自动搬运

查看原文

来自洛谷，原作者为

	Gabriel 登高必自卑，行远必自迩

搬运于2025-08-24 22:48:13，当前版本为作者最后更新于2023-06-24 09:09:39，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

先把每个 $id$ 的人数统计好，然后 $id$ 的数量有两种情况：

• $id$ 数比二小。
• $id$ 数大于等于二。

把 $id$ 大于等于二的学生数减二用 $sum1$ 累加，$id$ 小于二的学生数用 $sum2$ 累加。

如果 $sum1>sum2$，则只要把 $id$ 相同且人数大于等于二的人的 $id$ 改掉即可，即输出 $sum1$。

如果 $sum1 \le sum2$，则把 $id$ 相同的人改掉后剩下的不符合题意，应把一半 $id$ 人数为一的改掉。即输出 $sum1+\dfrac{sum2-sum1}{2}$。

代码

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

const int N = 1e6 + 10;
typedef long long ll;

int a[N], cnt[N];
int n;
int sum1 = 0, sum2 = 0;

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		cnt[a[i]]++;
	}
	for (int i = 1; i <= 1e6; i++) {
		if (cnt[i] >= 2) {
			sum1 += (cnt[i] - 2);
		} else {
			sum2 += cnt[i];
		}
	}
	if (sum1 > sum2) {
		cout << sum1 << "\n";
	} else {
		cout << sum1 + (sum2 - sum1) / 2 << "\n";
	}
    return 0;
}