班级分组难题：最少修改多少同学 id 实现公平配对？

我们一步步分析这个问题。 --- ## 1. 题意理解 - 有 \( n \) 个同学（\( n \) 是偶数）。 - 每个同学有一个正整数 id \( a_i \)。 - 目标：通过修改尽量少的同学的 id，使得最终每个 id 出现恰好 2 次（即每个 id 对应一对同学）。 - 问最少修改多少人的 id。 --- ## 2. 关键点 - 最终状态：有 \( n/2 \) 种不同的 id，每种 id 恰好 2 个同学。 - 初始状态：可能有某些 id 出现 1 次、3 次、4 次等，也可能有 id 已经出现 2 次。 - 修改一个同学的 id，相当于让它离开原来的 id 组，加入另一个 id 组（或新建一个 id）。 --- ## 3. 思路 设初始时不同 id 的个数为 \( m \)，每个 id 的出现次数为 \( cnt[x] \)。 最终要求： 1. 每个 id 出现次数 = 2。 2. 总共有 \( n/2 \) 个不同的 id。 --- 3.1 分类讨论 - 如果某个 id 出现次数 > 2，那么多出来的部分必须修改成别的 id。 - 如果某个 id 出现次数 = 2，那么这一对已经符合要求，可以保留。 - 如果某个 id 出现次数 = 1，那么它必须与另一个出现次数为 1 的 id 配对，或者从 >2 的 id 中分过来一个。 --- 3.2 更直接的贪心方法 已知最终有 \( n/2 \) 个不同的 id，每个 id 出现 2 次。 所以最终不同 id 的个数是固定的 \( n/2 \)。 设初始不同 id 的个数为 \( m \)。 - 如果 \( m < n/2 \)，说明我们需要增加新的 id 种类，这需要从出现次数 >2 的 id 里分出来，或者把出现次数 =1 的 id 合并。 - 如果 \( m > n/2 \)，说明我们需要减少 id 种类，把某些 id 的人改成已有的 id。 但这里更简单的思路是： 定义： - 设 \( extra \) = 所有出现次数 >2 的 id 中，超出 2 的部分的总和。 例如 id=1 出现 4 次，则超出部分 = 2（因为要保留 2 个，改掉 2 个）。 - 设 \( single \) = 出现次数 =1 的 id 的个数。 --- 配对过程： 1. 对于出现次数 >2 的 id，多出来的人必须修改 id。这些多出来的人可以填补到出现次数 =1 的 id 上（让它们变成 2 次），也可以用来创建新的 id（如果最终 id 种类不够 \( n/2 \)）。 2. 出现次数 =1 的 id 需要另一个相同 id 的人来配对，这个“另一个人”要么来自另一个出现次数 =1 的 id（两个 single 配对，但这样会减少 id 种类），要么来自某个 >2 的 id 中多出来的人。 --- 计算最少修改人数： 一个更简洁的公式（来自类似题解）： 设 \( k = n/2 \) 是最终需要的不同 id 个数。 设初始不同 id 个数为 \( m \)。 我们需要最终有 \( k \) 种 id，每种 2 个。 考虑初始时已经配对好的 id（出现次数 =2 的 id），假设有 \( p \) 个这样的 id。 那么这些 id 已经符合要求，不需要修改。 剩下的 \( n - 2p \) 个人需要调整，使得最终总共有 \( k \) 种 id。 --- 另一种常见贪心： 1. 统计出现次数 ≥2 的 id 中，保留 2 个，多出来的都要改。 设 \( s \) = 所有出现次数 >2 的 id 中，超出 2 的部分的总人数。 2. 统计出现次数 =1 的 id 个数 \( t \)。 最终 id 种类数 = \( m \) 初始，我们需要 \( k \) 种。 如果 \( m > k \)，我们必须减少种类，减少的方式是把某些出现次数 =1 的 id 的人改成已有的 id（这样会消除一个种类）。 如果 \( m < k \)，我们需要增加种类，增加的方式是把某些 >2 的 id 中多出来的人改成新的 id。 --- 具体计算： 设 \( more = \sum_{cnt>2} (cnt - 2) \) 表示“可用的多余人数”（他们必须改 id）。 设 \( needPair = \sum_{cnt=1} 1 \) 表示落单的人数（每个落单的人需要一个同伴）。 我们优先用多余的人去配对落单的人： - 如果 \( more \ge needPair \)，那么所有落单的人都可以被多余的人配对（配对时落单的人不需要改 id，多余的人改 id 来配对他们），这样落单的人不需要改 id，多余的人中有一部分改 id 去配对，剩下的多余的人需要改 id 去创建新的 id 种类（如果最终种类不够）。 - 如果 \( more < needPair \)，那么落单的人中有一部分需要互相配对（这样会减少 id 种类），另一部分被多余的人配对。 --- 但更简单的结论（经过推导）： 最少修改次数 = \[ \max\left( \sum_{cnt>2} (cnt-2),\ m - \frac{n}{2} \right) + \text{adjust} \] 实际上标准答案是： \[ \text{ans} = \max\left( \sum_{cnt>2} (cnt-2),\ m - \frac{n}{2} \right) \] 因为 \( m - n/2 \) 表示初始种类比最终种类多多少，这些多出来的种类必须消除，消除的方法是修改其中某些人的 id（每消除一个种类至少改 1 人）。 而 \( \sum_{cnt>2} (cnt-2) \) 表示必须改的人数下限（因为超出 2 的部分必须改）。 两者取最大就是答案。 --- ## 4. 验证样例 n=4, a=[1,2,2,3] cnt: 1→1, 2→2, 3→1 m=3 n/2=2 m - n/2 = 1 sum(cnt>2 的超出部分) = 0 max(0,1)=1 输出 1，符合样例。 --- ## 5. 代码实现 ```python from collections import Counter def solve(): n = int(input()) arr = list(map(int, input().split())) cnt = Counter(arr) m = len(cnt) target_pairs = n // 2 # 计算超出 2 的部分 extra = 0 for v in cnt.values(): if v > 2: extra += v - 2 ans = max(extra, m - target_pairs) print(ans) if __name__ == "__main__": solve() ``` ######[AI问答 | 1604点数解答 | 2026-01-11 13:28:28]