传送门
题目要求进行最大不同数字匹配数量,那么考虑贪心策略。
- 针对出现次数少的数字,那么应该和出现次数多的数字排,因为只有这样才能保证多的能被消除,假设是少的和少的匹配,那么当少的尽可能匹配完之后,出现次数多的就废了,这样就不是最优了。
- 也就是说,每次都对当前出现次数最多的两个数字进行一次消除,每次消除答案就-2,考虑使用优先队列储存,那么易得最后一定会出现全部消除完或者只剩一 (
个) 种数字的情况,由此代码得出。
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 +10;
int a[N];
void solve(){
priority_queue<pair<int, int> >pq;
map<int, int> mp;
int n;
cin >> n;
for(int i = 1; i <= n; i ++){
int x;
cin >> x;
mp[x] ++;
}
for(auto [x, y] : mp){
pq.push({y, x});
}
int size = n;
while(pq.size() >= 2){
auto temp1 = pq.top();
pq.pop();
auto temp2 = pq.top();
pq.pop();
temp1.first --;
temp2.first --;
size -= 2;
if(temp1.first){
pq.push(temp1);
}
if(temp2.first){
pq.push(temp2);
}
}
cout << size << "\n";
}
int main()
{
int t;
cin >> t;
while(t --){
solve();
}
return 0;
}