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