小明的老师准备组织一次班级活动。班上一共有 n 名（n 为偶数）同学， 老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 n 以内的正整数作为 id，第 i 名同学的 id 为 。 老师希望通过更改若干名同学的 id 使得对于任意一名同学 i，有且仅有另一名同学 j 的 id 与其相同（） 。请问老师最少需要更改多少名同学的 id？ 输入 输入共 2 行。 第一行为一个正整数 n。 第二行为 n 个由空格隔开的整数 a1, a2, ..., an。 数据范围： 对于 20% 的数据，保证 。 对于 100% 的数据，保证 。 输出 输出共 1 行，一个整数 样例输入 复制 4 1 2 2 3 样例输出 复制 1 提示 仅需要把 a1 改为 3 或者把 a3 改为 1 即可。

我们需要将 n 名学生（n 为偶数）分组，每组两人，且每组的两人 id 相同。 初始时每个学生有一个 id，可以更改任意学生的 id，目标是让每个 id 恰好出现两次，并且所有学生都被配对。 问最少更改多少名学生的 id。 --- ## 思路分析 设 n = 2k（k 是正整数）。 最终状态是：有 k 个不同的 id，每个 id 出现恰好 2 次。 初始时，统计每个 id 出现的次数。 设 id 的种类数为 m，每个 id 的出现次数为 cnt[x]。 --- 情况分类 1. 如果某个 id 出现次数 ≥ 2 我们可以保留其中 2 个学生不改，多出来的部分必须改掉（因为最终每个 id 只能有 2 个学生）。 2. 如果某个 id 出现次数 = 1 这个学生必须与另一个相同 id 的学生配对，所以要么改这个学生的 id，要么改另一个学生的 id 来匹配它。 但更优的策略是：把出现次数为 1 的 id 的学生与另一个出现次数为 1 的 id 的学生配对（通过改其中一个的 id 为对方 id），这样一次更改可以解决两个“单身”学生。 3. 如果某个 id 出现次数 = 0 这个 id 可用作目标 id，用来接收被更改的学生。 --- 计算最少更改数 设： - `single` = 出现次数为 1 的 id 的数量（即只有一个学生使用该 id 的数量）。 - `more` = 所有出现次数 ≥ 2 的 id 中，超出 2 的部分的总和（即这些 id 总共多出来的学生数）。 配对“单身”学生： 每两个单身学生可以通过一次更改配对（把其中一个的 id 改为另一个的 id）。 如果 single 是偶数，需要 single/2 次更改。 如果 single 是奇数，则 single/2 次更改后还剩一个单身学生，这个单身学生可以与一个“多余”学生配对，或者与一个“空缺” id 配对。 处理“多余”学生： 每个出现次数 > 2 的 id 会多出 cnt - 2 个学生需要改 id。 这些多余学生可以填补空缺 id（每个空缺 id 需要 2 个学生，但我们可以从多余学生中取 2 个改成这个空缺 id，这需要 2 次更改吗？不，如果空缺 id 原本 0 个学生，要放 2 个学生进去，需要改 2 个学生的 id 到这个空缺 id）。 --- 更系统的做法： 最终我们需要 k 个不同的 id，每个 id 恰好 2 个学生。 初始有 m 个不同的 id。 设 `c2` = 出现次数恰好为 2 的 id 的数量（这些 id 已经完成配对，不需要更改学生）。 设 `c1` = 出现次数为 1 的 id 的数量。 设 `c0` = 出现次数为 0 的 id 的数量（即 1..n 中没出现的数字，但注意 id 范围是 1..n 吗？题目说“n 以内的正整数”，所以可用 id 是 1..n，但初始给的 id 可能超过 n？不，题目说“n 以内的正整数”，所以 ai 在 1..n 之间。所以总共有 n 个可能的 id，但初始只用了其中一部分）。 --- 更简洁的贪心方法 定义： - `paired` = 已经配对好的学生数（即那些 id 出现次数 ≥ 2 的部分中，每个 id 取 2 个学生，这些学生已经配对）。 - `surplus` = 所有出现次数 ≥ 2 的 id 中，超出 2 的部分的总人数。 - `single` = 出现次数为 1 的 id 的数量（这些学生尚未配对）。 我们要把所有人配对。 已经配对好的学生数 = 2 * (出现次数 ≥ 2 的 id 的数量)？不对，因为出现次数 ≥ 2 的 id 中，每个可以贡献 2 个已配对学生，但可能这个 id 出现 4 次，则其中 2 个已配对，另外 2 个是 surplus。 --- 计算已配对学生数： 对于每个 id，如果 cnt ≥ 2，它可以提供 2 个已配对学生（不需要改），所以已配对学生数增加 2。 但注意，如果 cnt = 3，则 2 个已配对，1 个 surplus。 如果 cnt = 4，则 2 个已配对，2 个 surplus。 所以： ``` paired = sum_{cnt ≥ 2} 2 surplus = sum_{cnt ≥ 2} (cnt - 2) single = sum_{cnt = 1} 1 ``` 初始总学生数 n = paired + surplus + single。 --- 配对过程： 1. 用 surplus 去解决 single： 一个 surplus 学生可以改成某个 single 学生的 id，这样这个 single 学生就配对了（surplus 学生变成他的同伴），一次更改解决一个 single 学生。 如果 surplus ≥ single，则只需 single 次更改（每个 single 学生配一个 surplus 学生），然后剩下的 surplus 学生需要互相配对或与空缺 id 配对。 2. 如果 surplus < single： 先用 surplus 次更改解决 surplus 个 single 学生，剩下 single - surplus 个 single 学生。 这些剩下的 single 学生两两配对：每两个 single 学生通过一次更改（一个改成另一个的 id）完成配对。 所以需要 ceil((single - surplus) / 2) 次更改。 3. 处理剩下的 surplus（如果 surplus > single）： 先用掉 single 个 surplus 去配 single 学生，剩下 surplus - single 个 surplus 学生。 这些 surplus 学生需要与空缺 id 配对：每 2 个 surplus 学生可以配成一个新 id（需要 2 次更改，因为两个都改 id）。 所以需要 (surplus - single) 次更改吗？ 仔细想： 假设 surplus - single = t。 这些 t 个学生来自不同的 id（可能相同 id 有多个 surplus），我们要把他们分配到空缺 id 上。 每个空缺 id 需要 2 个学生。 如果 t 是偶数，需要 t 次更改（因为每个空缺 id 放 2 个学生，每个学生改一次 id，所以 2 个学生改 2 次，但这两个学生原本 id 不同，都要改成新 id）。 不对，再检查： 例：surplus 学生 id 是 A（A 已经有 2 个了），现在多出 1 个 surplus 学生 id A，要把他改成空缺 id B，这需要 1 次更改。另一个 surplus 学生 id C 也要改成空缺 id B，也需要 1 次更改。所以 2 个 surplus 学生配成一个新 id B 需要 2 次更改。 所以 t 个 surplus 学生需要 t 次更改（因为每个 surplus 学生都要改一次 id 到某个空缺 id，并且我们会安排他们成对进入同一个空缺 id）。 --- 公式： 设 single = s, surplus = p。 如果 p ≥ s： 先花 s 次更改把 s 个 single 学生与 s 个 surplus 学生配对。 剩下 p - s 个 surplus 学生，需要 p - s 次更改（每个改成某个空缺 id，成对安排）。 总更改 = s + (p - s) = p。 如果 p < s： 先花 p 次更改解决 p 个 single 学生。 剩下 s - p 个 single 学生，两两配对，需要 ceil((s - p)/2) 次更改。 总更改 = p + ceil((s - p)/2)。 --- 检查样例 n=4, a=[1,2,2,3] 统计： id 1: cnt=1 (single) id 2: cnt=2 (paired=2, surplus=0) id 3: cnt=1 (single) single s=2, surplus p=0。 p < s → 更改数 = 0 + ceil((2-0)/2) = 1。 匹配样例输出 1。 --- 验证另一个例子 n=6, a=[1,1,2,2,3,3] 所有 cnt=2，s=0, p=0 → 更改数=0。 n=6, a=[1,1,1,2,3,4] id1: cnt=3 → paired=2, surplus=1 id2: cnt=1 → single id3: cnt=1 → single id4: cnt=1 → single s=3, p=1。 p < s → 更改数 = 1 + ceil((3-1)/2) = 1+1=2。 检查： 把 id1 的一个 surplus 学生改成 id2，一次更改，id2 配对完成。 剩下 id3 和 id4 两个 single，一次更改（id3 改成 id4 或反之），完成。 总 2 次更改。 --- 最终算法 1. 统计每个 id 的出现次数 cnt。 2. 计算 s = 出现次数为 1 的 id 的数量。 3. 计算 p = sum_{cnt ≥ 2} (cnt - 2)。 4. 如果 p ≥ s，输出 p。 5. 否则输出 p + ceil((s - p) / 2)。 --- 代码实现 ```python import math n = int(input()) a = list(map(int, input().split())) cnt = {} for x in a: cnt[x] = cnt.get(x, 0) + 1 single = 0 surplus = 0 for v in cnt.values(): if v == 1: single += 1 elif v > 2: surplus += v - 2 if surplus >= single: print(surplus) else: print(surplus + (single - surplus + 1) // 2) ``` [2026-01-13 17:47:37 | AI问答 | 2266点数解答]