思路
用优先队列模拟
ac代码
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
const i64 inf = 8e18;
typedef pair<int, int> pii;
const int N = 5e5 + 10;
void solve() {
int n;
cin >> n;
map<int, int> mp;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
mp[x] ++;
}
priority_queue<pii> q;
for (auto [x, y] : mp)
q.push({y, x});
int ans = n;
while (q.size() >= 2) {
auto [x1, y1] = q.top();
q.pop();
auto [x2, y2] = q.top();
q.pop();
x1 --;
x2 --;
if (x1) q.push({x1, y1});
if (x2) q.push({x2, y2});
ans -= 2;
}
cout << ans << endl;
}
int main() {
ios::sync_with_stdio(0); cin.tie(0);
cout.tie(0);
int t = 1;
cin >> t;
while (t --) solve();
return 0;
}