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，则：

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

$$max{a}-(\sum ^n_{i=1}a_i-max{a})$$

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

所以最后答案就是

$$max{\sum ^n_{i=1}a_i-max{a}，n%2}$$

代码

#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();
	}
}