问题描述
小明的老师准备组织一次班级活动。班上一共有 n 名同学（n 为偶数），老师想把所有同学进行分组，每两名同学一组。
为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id，第 i 名同学的 id 为 a_i。
老师希望通过更改若干名同学的 id，使得对于任意一名同学 i，有且仅有另一名同学 j 的 id 与其相同（即 a_i = a_j）。
请问老师最少需要更改多少名同学的 id？
输入格式
共 2 行：
- 第 1 行：一个正整数
n（偶数）。 - 第 2 行：
n个由空格隔开的整数a_1, a_2, ..., a_n。
输出格式
- 输出 1 行，一个整数，表示最少需要更改多少名同学的
id。
样例输入
4
1 2 2 3
样例输出
1
样例说明
只需要将 a_1 改为 3，或者将 a_3 改为 1，即可满足每个 id 出现恰好两次。
评测用例规模与约定
- 对于 20% 的数据，保证
n ≤ 10^3 - 对于 100% 的数据，保证
n ≤ 10^5
#include<bits/stdc++.h>
#include<stdio.h>using namespace std;int n, a = 0, b = 0, r, ans = 0;
vector<int> arr;int main() {scanf("%d", &n);arr = vector<int>(n);for (int i = 0; i < n; i++) {scanf("%d", &arr[i]);}sort(arr.begin(), arr.end());for (int i = 0; i < n;) {r = i;while(r < n && arr[r] == arr[i]) r++;if (r - i > 2) a += (r - i - 2);else if (r - i == 1) b++;i = r;}if (a >= b) {ans += b;a -= b;ans += a;}else {ans += a;b -= a;ans += b / 2;}cout << ans;return 0;
}
思路解析
我的理解是贪心算法
对于多出来的，也就是出现次数大于2的，一定要修改一次，如果不修改，则会和前面两个一对矛盾，因为只能有两个一样。
对于少的，不够的，可以修改可以不修改，可以让多出来的和它一组，也可以让其他少的和它一组。
贪心策略就是尽量让多的和少的一组，如果还剩下多的，这些多的全部再修改一次变成其他数，如果剩下少的，只要修改n / 2次，因为他们本来就不重复
