问题描述

小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id，第 i 名同学的 id 为 ai​。

老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 j 的 id 与其相同 (ai=aj)。请问老师最少需要更改多少名同学的 id？

输入格式

输入共 2 行。

第一行为一个正整数 n。

第二行为 n 个由空格隔开的整数 a1,a2,...,an​。

输出格式

输出共 1 行，一个整数。

样例输入

4
1 2 2 3

样例输出

1

样例说明

仅需要把 a1​ 改为 3 或者把 a3 改为 1 即可。

评测用例规模与约定

解题代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];                // 存储每个同学的 id
map<int, int> m;         // 统计每个 id 出现的次数int main() {int n;cin >> n;for (int i = 1; i <= n; i++) {cin >> a[i];m[a[i]]++;       // 统计每个 id 出现的次数}int cnt1 = 0;        // 统计出现次数为 1 的 id 数量int cnt2 = 0;        // 统计出现次数大于 2 的 id 中需要更改的数量int cnt = 0;         // 最终需要更改的 id 数量// 遍历 map，统计 cnt1 和 cnt2for (auto& pair : m) {if (pair.second == 1) {cnt1++;      // 统计出现次数为 1 的 id 数量} else if (pair.second > 2) {cnt2 += (pair.second - 2); // 统计出现次数大于 2 的 id 中需要更改的数量}}//判断更改的总数//若大于2 的ID总数大于等于1 的//最后和1配对完的所有数均要更改if(cnt2>cnt1){cnt=cnt2;}//若大于2 的ID总数小于等于1 的//最后等于1的两两配对else{cnt=(cnt1-cnt2)/2+cnt2;}cout << cnt ; return 0;
}

1. 理解问题

• 目标：将 n 名同学分成 n/2 组，每组两人的 id 相同。

• 限制：每个 id 出现的次数必须是偶数次（即每个 id 出现两次）。

• 操作：通过更改某些同学的 id，使得所有 id 的出现次数满足上述条件。

---

2. 分析 id 出现次数的分布

• 统计每个 id 出现的次数。

• 将 id 的出现次数分为以下几类：

  1. 出现次数为 1：这些 id 必须被更改，因为无法单独成对。

  2. 出现次数为 2：这些 id 已经满足条件，无需更改。

  3. 出现次数大于 2：这些 id 需要减少出现次数，使其变为 2。

---

3. 确定需要更改的 id 数量

• 出现次数为 1 的 id：

  • 这些 id 必须被更改，因为无法单独成对。

  • 如果有 cnt1 个出现次数为 1 的 id，则需要至少 cnt1 / 2 次更改（两两配对）。

• 出现次数大于 2 的 id：

  • 这些 id 需要减少出现次数，使其变为 2。

  • 如果一个 id 出现 k 次（k > 2），则需要更改 k - 2 次。

• 综合计算：

  • 如果出现次数大于 2 的 id 需要更改的总次数 cnt2 大于等于出现次数为 1 的 id 数量 cnt1，则总更改次数为 cnt2。

  • 否则，总更改次数为 (cnt1 - cnt2) / 2 + cnt2。

4. 代码分析注释

1. 输入数据：

   • 使用数组 a[N] 存储每个同学的 id。

   • 使用 map<int, int> m 统计每个 id 出现的次数。

2. 统计 id 出现次数：

   • 遍历数组 a，将每个 id 的出现次数记录在 map 中。

3. 统计 cnt1 和 cnt2：

   • cnt1：统计出现次数为 1 的 id 数量。

   • cnt2：统计出现次数大于 2 的 id 中需要更改的数量。例如，如果一个 id 出现 4 次，则需要更改 4 - 2 = 2 次。

4. 计算需要更改的 id 数量：

   • 情况 1：如果 cnt2 >= cnt1，即出现次数大于 2 的 id 数量大于等于出现次数为 1 的 id 数量，则需要更改的总数为 cnt2。

   • 情况 2：如果 cnt2 < cnt1，则需要将多余的 cnt1 - cnt2 个出现次数为 1 的 id 两两配对，每对需要更改 1 次，因此总更改次数为 (cnt1 - cnt2) / 2 + cnt2。

5. 输出结果：

   • 输出需要更改的 id 数量。