班级活动分组难题：最少修改多少学生 ID 实现公平分组？

题意理解 n 名学生，每名学生有一个正整数 id（范围在 n 以内）。 目标：通过修改一些学生的 id，使得最终每个 id 恰好出现两次（即 n/2 个不同的 id，每个 id 恰好对应 2 名学生）。 问最少修改多少名学生的 id。 --- 思路分析 1. 最终状态：有 n/2 个不同的 id，每个 id 出现 2 次。 2. 当前状态：统计每个 id 出现的次数。 3. 修改学生 id 相当于： - 减少某些 id 的出现次数（把多出来的学生改成别的 id）。 - 增加某些 id 的出现次数（把别的学生改成这个 id）。 等价于： - 设最终保留的 id 集合为 S，|S| = n/2。 - 对于每个最终保留的 id，它当前可能已经有若干学生拥有它，如果当前拥有它的学生数 ≤ 2，则只需补足到 2 个；如果 > 2，则必须把多出的学生改成别的 id。 - 最终保留的 id 从当前已有的 id 中选择一部分，不足 n/2 个时，可以引入新的 id（1~n 中未出现的 id）。 --- 贪心策略 1. 统计每个 id 出现的次数，按出现次数从大到小排序。 2. 优先保留出现次数多的 id（因为保留它们可以减少修改次数）。 3. 最终保留 n/2 个 id，每个 id 最终要有 2 个学生。 对于每个保留的 id： - 如果当前有 c 个学生，c ≥ 2，则保留 2 个，多出的 c-2 个学生必须修改 id。 - 如果 c = 1，则保留 1 个，还需要 1 个学生改成这个 id。 - 如果 c = 0，则这个 id 是新增的，需要 2 个学生改成这个 id。 4. 计算最少修改数： 设当前有 m 个不同的 id（m ≤ n）。 我们选择保留 k 个已有的 id（k ≤ n/2），那么新增的 id 数量 = n/2 - k。 对于保留的 id，如果它的当前数量为 c，则它贡献的修改数 = max(0, c-2)（多出的要改走） + max(0, 2-c)（不足的要补来）。 但注意：补来的学生从哪里来？从那些被改走的学生中来。 所以更简单的计算方式： - 总共有 n 个学生。 - 最终每个保留的 id 有 2 个学生，所以最终保留的学生总数 = n（显然）。 - 对于每个最终保留的 id，如果当前有 c 个学生，则至少保留 min(c, 2) 个学生不动，其余学生要改成别的 id 或者从别的 id 改过来。 换个角度： 最少修改数 = n - （最多可以保留不动的学生数）。 最多可以保留不动的学生数 = 对每个最终保留的 id，最多保留 min(c, 2) 个学生不动。 所以我们要选择 n/2 个 id（可以重复吗？不行，id 必须不同），使得 sum(min(c_i, 2)) 最大。 因为 min(c_i, 2) ≤ 2，所以每个 id 最多贡献 2 个不动的学生。 我们要选 n/2 个 id，所以最大不动的学生数 ≤ n。 具体选法：优先选那些 c_i ≥ 2 的 id，因为它们可以贡献 2 个不动的学生；如果不够 n/2 个，再选 c_i = 1 的 id，贡献 1 个不动的学生。 设： - cnt2 = 当前出现次数 ≥ 2 的 id 数量（每个这样的 id 可以贡献 2 个不动的学生）。 - cnt1 = 当前出现次数 = 1 的 id 数量（每个这样的 id 可以贡献 1 个不动的学生）。 - 其他出现次数 = 0 的 id 可以贡献 0 个不动的学生。 我们要选 n/2 个 id： 如果 cnt2 ≥ n/2，则我们选 n/2 个出现次数 ≥ 2 的 id，每个贡献 2 个不动的学生，所以不动的学生数 = 2*(n/2) = n，修改数 = 0（但可能吗？如果 cnt2 ≥ n/2 且每个 id 出现次数 ≥ 2，但总人数可能超过 n？不会，因为总人数固定 n，如果 cnt2 ≥ n/2，每个至少 2 人，总人数至少 2*(n/2)=n，所以恰好每个 id 出现 2 次，已经满足条件，修改数 0）。 如果 cnt2 < n/2，则我们先选所有 cnt2 个 id（贡献 2*cnt2 个不动的学生），还需要选 (n/2 - cnt2) 个 id，从 cnt1 中选，每个贡献 1 个不动的学生。 所以不动的学生数 = 2*cnt2 + min(cnt1, n/2 - cnt2)。 修改数 = n - [2*cnt2 + min(cnt1, n/2 - cnt2)]。 注意：如果 cnt1 < n/2 - cnt2，则我们还需要选一些出现次数 0 的 id，它们贡献 0 个不动的学生。 --- 举例验证 样例：n=4, ids=[1,2,2,3] 统计： id=1 出现 1 次 → cnt1=1 id=2 出现 2 次 → cnt2=1 id=3 出现 1 次 → cnt1=2 所以 cnt2=1, cnt1=2。 n/2=2。 cnt2=1 < 2，所以不动的学生数 = 2*1 + min(2, 2-1) = 2 + 1 = 3。 修改数 = 4 - 3 = 1。符合样例输出。 --- 算法步骤 1. 读入 n 和数组 a。 2. 统计每个 id 的出现次数（id 范围 1~n，因为题目说 n 以内的正整数）。 3. 计算 cnt2 = 出现次数 ≥ 2 的 id 数量，cnt1 = 出现次数 = 1 的 id 数量。 4. 计算不动学生数： if cnt2 >= n/2: 不动 = n else: 不动 = 2*cnt2 + min(cnt1, n/2 - cnt2) 5. 输出 n - 不动。 --- 代码实现 ```python n = int(input()) a = list(map(int, input().split())) # 统计出现次数 freq = [0] * (n + 1) for x in a: freq[x] += 1 cnt2 = 0 cnt1 = 0 for i in range(1, n + 1): if freq[i] >= 2: cnt2 += 1 elif freq[i] == 1: cnt1 += 1 half = n // 2 if cnt2 >= half: unchanged = n else: unchanged = 2 * cnt2 + min(cnt1, half - cnt2) print(n - unchanged) ``` ######[AI问答 | 1692点数解答 | 2026-01-13 17:49:24]