CF1506C Epic Transformation

Epic Transformation - 洛谷

算是今天的题目里边思维难度最高的一道了，但是代码真的简单的要死

题意

你有一个长度为 \(n\) 的序列 \(a\)，你可以对其进行下列操作：

• 选择 \(i,j\) 满足 \(a_i\neq a_j\) 然后删除 \(*a_i,a_j*\) 两个数。

求序列 a 经过若干次操作后最少有几个数，\(*T*\) 组数据。

\(1≤T≤10^4;1≤n,∑n≤2×10^5;1≤a_i≤10^9\)

思路

其实 证明 或 推导 更合适一些

这题，可以构造，当有\(n\)个数时，如果\(n\)为奇数，那么输出最小为\(1\)，为偶数时，最小为\(0\)

那，如何构造呢？通过最大的一堆将其余的\(n-1\)堆变得相等即可。

设各数出现次数为数列a，则：

1. 若\(max\{a\}>\sum ^n_{i=1}a_i-max\{a\}\)：则最大的一种数无法被消完时其余各数串已经相等，答案为

2. 若\(max\{a\}<\sum ^n_{i=1}a_i-max\{a\}\)：说明可以消干净，答案因奇偶而定

所以最后答案就是

代码

#include<bits/stdc++.h>
using namespace std;
const int maxx=2e5+10;
int n,a[maxx],maxn,cnt;
int run()
{
	maxn=0,cnt=1;
	cin>>n;
	for(int i=0;i<n;i++) cin>>a[i];
	sort(a,a+n);
	for(int i=0;i<n-1;i++)
	{
		if(a[i]==a[i+1]) cnt++;
		else
		{
			maxn=max(maxn,cnt);
			cnt=1;
		}
	}
	maxn=max(maxn,cnt);
//	cout<<maxn<<endl; 
	cout<<max(maxn-(n-maxn),n%2)<<endl;
	return 0;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		run();
	}
}