首页 > 其他分享 >每日一题 第二十六期 Codeforces Round 936 (Div. 2)

每日一题 第二十六期 Codeforces Round 936 (Div. 2)

时间:2024-03-23 10:33:38浏览次数:28  
标签:int median number Codeforces Round test Div include array

A. Median of an Array

time limit per test: 1 second

memory limit per test: 256 megabytes

input: standard input

output: standard output

You are given an array a a a of n n n integers.

The median of an array q 1 , q 2 , … , q k q_1, q_2, \ldots, q_k q1​,q2​,…,qk​ is the number p ⌈ k 2 ⌉ p_{\lceil \frac{k}{2} \rceil} p⌈2k​⌉​, where p p p is the array q q q sorted in non-decreasing order. For example, the median of the array [ 9 , 5 , 1 , 2 , 6 ] [9, 5, 1, 2, 6] [9,5,1,2,6] is 5 5 5, as in the sorted array [ 1 , 2 , 5 , 6 , 9 ] [1, 2, 5, 6, 9] [1,2,5,6,9], the number at index ⌈ 5 2 ⌉ = 3 \lceil \frac{5}{2} \rceil = 3 ⌈25​⌉=3 is 5 5 5, and the median of the array [ 9 , 2 , 8 , 3 ] [9, 2, 8, 3] [9,2,8,3] is 3 3 3, as in the sorted array [ 2 , 3 , 8 , 9 ] [2, 3, 8, 9] [2,3,8,9], the number at index ⌈ 4 2 ⌉ = 2 \lceil \frac{4}{2} \rceil = 2 ⌈24​⌉=2 is 3 3 3.

You are allowed to choose an integer i i i ( 1 ≤ i ≤ n 1 \le i \le n 1≤i≤n) and increase a i a_i ai​ by 1 1 1 in one operation.

Your task is to find the minimum number of operations required to increase the median of the array.

Note that the array a a a may not necessarily contain distinct
numbers.
Input

Each test consists of multiple test cases. The first line contains a single integer t t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer n n n ( 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105) — the length of the array a a a.

The second line of each test case contains n n n integers a 1 , a 2 , … , a n a_1, a_2, \ldots, a_n a1​,a2​,…,an​ ( 1 ≤ a i ≤ 1 0 9 1 \le a_i \le 10^9 1≤ai​≤109) — the array a a a.

It is guaranteed that the sum of the values of n n n over all test cases does not exceed 2 ⋅ 1 0 5 2 \cdot 10^5 2⋅105.

Output

For each test case, output a single integer — the minimum number of operations required to increase the median of the array.

Example
inputCopy
8
3
2 2 8
4
7 3 3 1
1
1000000000
5
5 5 5 4 5
6
2 1 2 3 1 4
2
1 2
2
1 1
4
5 5 5 5
outputCopy
1
2
1
3
2
1
2
3

Note

In the first test case, you can apply one operation to the first number and obtain the array [ 3 , 2 , 8 ] [3, 2, 8] [3,2,8], the median of this array is 3 3 3, as it is the number at index ⌈ 3 2 ⌉ = 2 \lceil \frac{3}{2} \rceil = 2 ⌈23​⌉=2 in the non-decreasing sorted array [ 2 , 3 , 8 ] [2, 3, 8] [2,3,8]. The median of the original array [ 2 , 2 , 8 ] [2, 2, 8] [2,2,8] is 2 2 2, as it is the number at index ⌈ 3 2 ⌉ = 2 \lceil \frac{3}{2} \rceil = 2 ⌈23​⌉=2 in the non-decreasing sorted array [ 2 , 2 , 8 ] [2, 2, 8] [2,2,8]. Thus, the median increased (KaTeX parse error: Expected 'EOF', got '&' at position 3: 3 &̲gt; 2) in just one operation.

In the fourth test case, you can apply one operation to each of the numbers at indices 1 , 2 , 3 1, 2, 3 1,2,3 and obtain the array [ 6 , 6 , 6 , 4 , 5 ] [6, 6, 6, 4, 5] [6,6,6,4,5], the median of this array is 6 6 6, as it is the number at index ⌈ 5 2 ⌉ = 3 \lceil \frac{5}{2} \rceil = 3 ⌈25​⌉=3 in the non-decreasing sorted array [ 4 , 5 , 6 , 6 , 6 ] [4, 5, 6, 6, 6] [4,5,6,6,6]. The median of the original array [ 5 , 5 , 5 , 4 , 5 ] [5, 5, 5, 4, 5] [5,5,5,4,5] is 5 5 5, as it is the number at index ⌈ 5 2 ⌉ = 2 \lceil \frac{5}{2} \rceil = 2 ⌈25​⌉=2 in the non-decreasing sorted array [ 4 , 5 , 5 , 5 , 5 ] [4, 5, 5, 5, 5] [4,5,5,5,5]. Thus, the median increased (KaTeX parse error: Expected 'EOF', got '&' at position 3: 6 &̲gt; 5) in three operations. It can be shown that this is the minimum possible number of operations.

In the fifth test case, you can apply one operation to each of the numbers at indices 1 , 3 1, 3 1,3 and obtain the array [ 3 , 1 , 3 , 3 , 1 , 4 ] [3, 1, 3, 3, 1, 4] [3,1,3,3,1,4], the median of this array is 3 3 3, as it is the number at index ⌈ 6 2 ⌉ = 3 \lceil \frac{6}{2} \rceil = 3 ⌈26​⌉=3 in the non-decreasing sorted array [ 1 , 1 , 3 , 3 , 3 , 4 ] [1, 1, 3, 3, 3, 4] [1,1,3,3,3,4]. The median of the original array [ 2 , 1 , 2 , 3 , 1 , 4 ] [2, 1, 2, 3, 1, 4] [2,1,2,3,1,4] is 2 2 2, as it is the number at index ⌈ 6 2 ⌉ = 3 \lceil \frac{6}{2} \rceil = 3 ⌈26​⌉=3 in the non-decreasing sorted array [ 1 , 1 , 2 , 2 , 3 , 4 ] [1, 1, 2, 2, 3, 4] [1,1,2,2,3,4]. Thus, the median increased (KaTeX parse error: Expected 'EOF', got '&' at position 3: 3 &̲gt; 2) in two operations. It can be shown that this is the minimum possible number of operations.

AC代码:

#include<map>
#include<set>
#include<stack>
#include<cmath>
#include<queue>
#include<string>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<numeric>
#include<iomanip>
#define endl '\n'
using namespace std;

typedef long long ll;
typedef pair<int, int>PII;
const int N=3e5+10;
const int MOD=998244353;
const int INF=0X3F3F3F3F;
const int dx[]={-1,1,0,0,-1,-1,+1,+1};
const int dy[]={0,0,-1,1,-1,+1,-1,+1};
const int M = 1e6 + 10;

int t;
int n;
int a[N];
int main()
{
	cin >> t;
	while(t --){
		int n;
		cin >> n;
		for(int i = 1; i <= n; i++)
		{
			cin >> a[i];
		}
		sort(a + 1, a + 1 + n);
		if(n & 1)
		{
			int cnt = 1;
			for(int i = (n + 1) / 2; i <= n; i ++)
			{
				if(a[i] == a[i + 1] && i != n) cnt ++ ;
				else break;
			}
			cout << cnt << endl;
		}
		else {
			int cnt = 1;
			for(int i = n / 2; i <= n; i ++)
			{
				if(a[i] == a[i + 1] && i != n) cnt ++;
				else break;
			}
			cout << cnt << endl;
		}
	}
	return 0;
}

标签:int,median,number,Codeforces,Round,test,Div,include,array
From: https://blog.csdn.net/2301_80882026/article/details/136961807

相关文章

  • 每日一题 第二十七期 Codeforces Round 936 (Div. 2)
    B.MaximumSumtimelimitpertest:1secondmemorylimitpertest:256megabytesinput:standardinputoutput:standardoutputYouhaveanarrayaaaof......
  • Codeforces Round 935 (Div. 3)
    A-SettingupCamp思路:判断c能否填充b让b为3的倍数查看代码voidsolve(){inta,b,c;cin>>a>>b>>c;intans=a+b/3;b%=3;if(b>0&&b+c<3)cout<<-1<<'\n';else{ans+=(b+c+2)/3;c......
  • loj#533. 「LibreOJ Round #6」花煎
    非常巧妙的转化。考虑仅计算半边的序列,那么这样的话\(len\)削了一半,要达成的色彩值也开平方了。问题就转化为,将\(l\)拆分为序列\(a\),使得\(\sum_{i=1}^{n}(a_i+1)=l\),且使得\(\prod_{i=1}^{n}a_i\geqk\)的最小\(l\)。经过一些计算,可以发现2的段不超过一个,3的段不......
  • cfRound935div3--DEFG题解
    ps:这场因为精神状态不佳,又C题题意有点绕,卡题了,头晕找不到错.最后做了两题就溜了.狠狠扣90分..D-SeraphimtheOwl题意:即选一个位置,使得其满足题意。而且在满足题意的基础上,要靠近中心越好,如果满足题意而且靠近中心的距离一样,那么输出前面那个.intcnt0[300005]={0};......
  • CF1920 Codeforces Round 919 (Div. 2)
    B.SummationGame给你\(n\)个数(均大于0),Alice先执行一次删除不超过\(k\)个数,Bob再执行一次把最多\(x\)个数变成相反数.问最后数组的最大和是多少?这题本来是想先让Alice删除\(k\)个数,但显然不太容易得到最优解,因为还有可能撤回Alice的删除操作,再加上Bob的操作.......
  • Codeforces Round 935 (Div. 3)
    A.SettingupCamp#include<bits/stdc++.h>usingnamespacestd;usingi32=int32_t;voidsolve(){inta,b,c;cin>>a>>b>>c;intres=a+b/3;b%=3;if(b!=0){if(c<3-b){......
  • 1943+1944.Codeforces Round 934 (Div. 1,Div. 2) - sol
    20240321终于差不多把Div1补完了(F当然没补),第一次打Div1,还是出了一些小状况的。唉。没有补Div1F的逆天题,选择放弃。Dashboard-CodeforcesRound934(Div.2)-CodeforcesDashboard-CodeforcesRound934(Div.1)-Codeforces2A.DestroyingBridgesThere......
  • Educational Codeforces Round 163 (Rated for Div. 2)
    Preface这周很奇怪,连着计网、数据库、组合数学的课都莫名其妙不上了,突然变得很空闲了的说正好有空赶紧补补题,不然接下来有很多造题/比赛的任务搁置着就忘记了A.SpecialCharacters签到,\(n\)是偶数才有解,构造的话注意到一个AAB可以产生\(2\)的贡献,把\(\frac{n}{2}\)个AAB拼起......
  • Tree Compass Codeforces Round 934 (Div. 2) 1944E
    Problem-E-Codeforces题目大意:有一棵n个点的树,初始状态下所有点都是白色的,每次操作可以选择一个点u和一个距离dis,使得距离点u所有长度为dis的点变为黑色,问最少需要多少次操作能使所有点变成黑色,输出所有操作1<=n<=2000思路:要想操作数最少,就要使每次操作涂黑的点的数量尽......
  • HDU 1059 Dividing
    题目传送门:Problem-1059(hdu.edu.cn)问题描述玛莎和比尔拥有一些弹珠。他们希望在自己之间分配收藏品,以便双方都获得平等的弹珠份额。如果所有弹珠都具有相同的价值,这将很容易,因为这样他们就可以将收藏品分成两半。但不幸的是,有些弹珠比其他弹珠更大或更漂亮。因此,Marsha......