我叶梓楣也要成为duck大魔王！！！（1）

这道题这里提供两种做法：

第一种：

第一种是找规律 我们通过手模可以发现 考虑最极端的情况 当n==n/2 然后再去想大于和小于

1.n<=n/2

如果n为偶数 一个数字出现的最大次数等于n/2，那么答案肯定为0

如果n为奇数 那么 肯定为1 最后剩下一个

比如说：1 1 3 3 3 5 5 1

5 和 1 5和3 然后31 就消完了 可以自己多举个例子 想想 会发现确实是这样的

2.如果x>n/2:

n-max 是可以用与消的数嘛 然后 每用一个 数组长度-2 所以得到了这个公式

n-2*(n-max)

/*
  * @Author: duck
  * @Date: 2025-11-03 09:59:50
  */
 #include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; // 正好等于2的60次方
 typedef pair<int, int> pii;
 const int N = 2E5 + 10;
 int vec[N];
 void solve()
 {
     int n;
     cin >> n;
     for (int i = 1; i <= n; i++)
     {
         cin >> vec[i];
     }
 ​
     sort(vec + 1, vec + 1 + n);
     // 不会sort 你们改成冒泡就好了 就是从小到大 排个序
 ​
     int mx = 0;
     int sum = 1;
     for (int i = 1; i + 1 <= n; i++)
     {
         if (vec[i] != vec[i + 1])
         {
             mx = max(sum, mx);
             sum = 1;
         }
         else
         {
             sum++;
         }
     }
     mx = max(sum, mx);
 ​
     if (mx > n / 2)
     {
         cout << n - 2 * (n - mx) << endl;
     }
     else
     {
         if (n % 2)
         {
             cout << 1 << endl;
         }
         else
         {
             cout << 0 << endl;
         }
     }
 }
 ​
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     cin >> t;
     while (t--)
     {
         solve();
     }
     return 0;
 }

第二种：（扩展内容）

我看有人用桶去写，这道题确实可以用桶的思想去写 但是这道题的数据大小是有1e9的啊 我们之前讲过 数组大小是开不到1e9的 那用桶不就炸了

所以在这里的话 我们考虑 如何把1e9存起来 这里有两种方法：

第一种是用STL map去存 map是可以存1e9大小的 然后思想和第一种是一样的

第二种是我们通过离散化 将1e9 重新赋值 这样下标就小了 因为 我们并不想要这个数值 我们只是想知道这个数字数量是多少 那么我们n最大为2e5 肯定就可以开桶了 是没想到这个规律的暴力方法

上面说的map和离散化未讲 只是给大家扩展思路 想提前学的可以去了解

map写法

​
 /*
  * @Author: duck
  * @Date: 2025-11-03 09:59:50
  */
 #include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; // 正好等于2的60次方
 typedef pair<int, int> pii;
 const int N = 2E5 + 10;
 int vec[N];
 void solve()
 {
     int n;
     cin >> n;
     map<int, int> vis;
     int mx = 0;
     for (int i = 1; i <= n; i++)
     {
         cin >> vec[i];
         vis[vec[i]]++;
         mx = max(mx, vis[vec[i]]);
     }
 ​
     if (mx > n / 2)
     {
         cout << n - 2 * (n - mx) << endl;
     }
     else
     {
         if (n % 2)
         {
             cout << 1 << endl;
         }
         else
         {
             cout << 0 << endl;
         }
     }
 }
 ​
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     cin >> t;
     while (t--)
     {
         solve();
     }
     return 0;
 }

离散化写法

这个写法是很暴力的一个写法 你没想到规律 然后模拟的去写这道题 每次都让最大的和次大的消 模拟这个过程 使用到了优先队列 也是给大家提供一种别的思路 没讲过 感兴趣的自己了解

#include <bits/stdc++.h>
 using namespace std;
 #define int long long
 #define ull unsigned long long
 #define endl '\n'
 #define EPS 1e-8
 #define fi first
 #define se second
 #define lowbit(x) x & (-x)
 const int inf = 0x3f3f3f3f3f3f3f3f; 
 typedef pair<int, int> pii;
 const int N = 2e5 + 10;
 int newa[N];
 struct QWQ
 {
     int val;
     int id;
 } olda[N];
 ​
 bool cmp(QWQ x, QWQ y)
 {
     return x.val < y.val;
 }
 ​
 void solve()
 {
     int n;
     cin >> n;
     vector<int> vec(n + 1);
     for (int i = 1; i <= n; i++)
     {
         cin >> olda[i].val;
         olda[i].id = i;
     }
 ​
     sort(olda + 1, olda + 1 + n, cmp);
 ​
     int idx = 0;
 ​
     for (int i = 1; i <= n; i++)
     {
         if (i == 1 || olda[i].val != olda[i - 1].val)
         {
             idx++;
         }
         newa[olda[i].id] = idx;
     }
 ​
     vector<int> b(n + 1);
     for (int i = 1; i <= n; i++)
     {
         b[newa[i]]++;
     }
 ​
     priority_queue<int> que;
     for (int i = 1; i <= idx; i++)
     {
         if (b[i] > 0)
         {
             que.push(b[i]);
         }
     }
 ​
     while (que.size() >= 2)
     {
         int tp1 = que.top();
         que.pop();
 ​
         int tp2 = que.top();
         que.pop();
 ​
         tp1--;
         tp2--;
 ​
         if (tp1 > 0)
         {
             que.push(tp1);
         }
 ​
         if (tp2 > 0)
         {
             que.push(tp2);
         }
     }
 ​
     int ans = 0;
 ​
     while (!que.empty())
     {
         ans += que.top();
         que.pop();
     }
 ​
     cout << ans << endl;
 ​
 }
 signed main()
 {
     ios::sync_with_stdio(false);
     cin.tie(0);
     cout.tie(0);
     int t = 1;
     cin >> t;
     while (t--)
     {
         solve();
     }
     return 0;
 }