1506D Epic Transformation

题面

给你一个长度为 \(n\) 的整数数组 \(a\)， 你可以进行 0 次或多次下列操作：

• 你选择两个不同的数字 \(a_i\) 和 \(a_j\)
• 然后你从数组中删除第 \(i\) 个和第 \(j\) 个元素

例如：\(n=6\) , \(a = [1,6,1,1,4,4]\) ，然后你执行以下操作：

• 选择 \(i = 1, j = 5\) ，然后数组 \(a\) 就变成了 \([6,1,1,4]\)
• 选择 \(i = 1 , j = 2\) ，然后数组 \(a\) 就变成了 \([1,4]\)

怎样操作能让数组的大小最小？ 输出最小长度可能为多少

思路

利用 \(map\) 映射来获取最多的数字的数量，将该数字数量记作 \(mx\)

根据贪心，我们可以得出以下结论

• 当 $ 2\times mx >n$ 的时候，\(mx\) 可以把其他数字全都消除，并且还会有剩余，余量即 $ 2mx -n$
• 当$ 2 \times mx <= n\(的时候，\)mx\(会被其他数字消除完，而其他数字的余量即\) n % 2$

标签

思维 CF 1400 贪心

代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main(){
	int T;
	cin >> T;
	while(T--){
		ll n;
		cin >> n;
		
		map<ll,ll> mp;
		ll mx = 0,x;
		for(int i = 0 ; i < n ; i++){
			cin >> x;
			mx = max(mx,++mp[x]);
		}
		
		cout << max(n%2,2*mx-n) << endl;
	}
}