本地的南通网站建设/提高工作效率的措施

1. 班级活动

前置知识点：思维，分类讨论

1. 问题描述

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

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

2. 输入格式

输入共 $2$ 行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格隔开的整数 $a_1,a_2,...,a_n$。

3. 输出格式

输出共 $1$ 行，一个整数。

4. 样例输入

4
1 2 2 3

5. 样例输出

1

6. 样例说明

仅需要把 $a_1$ 改为 $3$ 或者把 $a_3$ 改为 $1$ 即可。

7. 评测用例规模与约定

对于 $20\%$ 的数据，保证 $n\le 10^3$。

对于 $100\%$ 的数据，保证 $n\le 10^5$。

8. 原题链接

班级活动

2. 解题思路

首先明确一点，假设某个 $\text{id}$ 的同学数量为 $x(x>2)$，因为题目要求任意 $\text{id}$ 只能有两名同学，所以一定会有 $x-2$ 名同学修改自己的 $\text{id}$。我们可以计算出每个 $\text{id}$ 需要修改自身的同学数量之和，并将这个数量设为 $b$，即满足：
$$b=\sum _{i=1}^n\max (0,a_i-2)$$
还有一个特殊群体我们不能忽略，就是编号 $\text{id}$ 唯一的同学，我们设这群同学的数量为 $a$。他们特殊在有可能需要修改自身 $\text{id}$，也有可能不需要，我们需要进行分类讨论。

• 当 $b\ge a$ 时：

在这种情况下，$\text{id}$ 唯一的 $a$ 名同学是不需要修改自身 $\text{id}$ 的。我们可以从 $b$ 名同学中选出 $a$ 名同学修改自身 $\text{id}$ 去与 $\text{id}$ 唯一的同学对应，剩下的 $b-a$ 名同学仍然是需要修改自身 $\text{id}$ 的，所以答案即是 $b$。

假设有一个 $\text{id}$ 集合 A = { 1 , 2 , 3 , 4 , 4 , 4 , 4 , 5 , 5 , 5 , 5 , 5 } A= \lbrace1,2,3,4,4,4,4,5,5,5,5,5\rbrace A={1,2,3,4,4,4,4,5,5,5,5,5}，此时 $\text{id}$ 唯一的集合为 { 1 , 2 , 3 } \lbrace1,2,3\rbrace {1,2,3}，必须修改的 $\text{id}$ 集合为 { 4 , 4 , 5 , 5 , 5 } \lbrace4,4,5,5,5\rbrace {4,4,5,5,5}。我们只需要让后一个集合的 $\text{id}$ 分别修改为 { 1 , 2 , 3 , 6 , 6 } \lbrace 1,2,3,6,6\rbrace {1,2,3,6,6} 即可符合要求。

• 当 $b<a$ 时：

在这种情况下，部分 $\text{id}$ 唯一的 $a$ 名同学是需要修改自身 $\text{id}$ 的。同样假设有一个 $\text{id}$ 集合 A = { 1 , 2 , 3 , 4 , 5 , 5 , 5 , 5 , 5 , 5 , 6 , 7 } A=\lbrace1,2,3,4,5,5,5,5,5,5,6,7\rbrace A={1,2,3,4,5,5,5,5,5,5,6,7}，此时 $\text{id}$ 唯一的集合为 { 1 , 2 , 3 , 4 , 6 , 7 } \lbrace1,2,3,4,6,7\rbrace {1,2,3,4,6,7}，必须修改的 $\text{id}$ 集合为 { 5 , 5 , 5 , 5 } \lbrace5,5,5,5\rbrace {5,5,5,5}。按照同样策略，我们让必须修改的 $\text{id}$ 集合与 $\text{id}$ 唯一的集合对应上，即将必须修改的 $\text{id}$ 集合变为 { 1 , 2 , 3 , 4 } \lbrace1,2,3,4\rbrace {1,2,3,4}。

但此时仍然发现 $\text{id}$ 唯一的集合剩余的两个 $\text{id}$ 为 { 6 , 7 } \lbrace6,7\rbrace {6,7}，我们需要让他们它们一致，所以需要修改其中一个。

假设剩余 $4$ 个呢？那我们需要修改 $2$ 个。

假设剩余 $8$ 个呢？那我们需要修改 $4$ 个。

显然结论就是需要修改剩余 $\text{id}$ 个数的一半，即这种情况下答案是：
$$\frac{a-b}{2}+b$$
小疑问：如果 a-b 为奇数怎么办？

结论：$a-b$ 一定为偶数。我们可以假设数组已经存在 $c$ 对匹配好的 $\text{id}$，根据我们对 $a,b$ 的定义，显然符合式子 $a+b+2\times c=n$。题目告知我们 $n$ 一定为偶数，且 $2\times c$ 也一定为偶数，那么 $a+b$ 也一定为偶数，即说明 $a,b$ 奇偶性一定相同，得证 $a-b$ 一定为偶数。

时间复杂度：$O(n)$。

3. AC_Code

• C++

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;int n;
int main()
{cin >> n;map<int, int> cnt;for (int i = 0; i < n; ++i){int x;cin >> x;cnt[x]++;}int a = 0, b = 0;for (auto [x, y] : cnt){if (y == 1){a++;}else if (y > 2){b += y - 2;}}if (b >= a){cout << b << '\n';}else{cout << (a - b) / 2 + b << '\n';}return 0;
}

• Java

import java.util.*;public class Main {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();Map<Integer, Integer> cnt = new HashMap<>();for (int i = 0; i < n; ++i) {int x = sc.nextInt();cnt.put(x, cnt.getOrDefault(x, 0) + 1);}int a = 0, b = 0;for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {int y = entry.getValue();if (y == 1) {a++;} else if (y > 2) {b += y - 2;}}if (b >= a) {System.out.println(b);} else {System.out.println((a - b) / 2 + b);}}
}

• Python

n = int(input())
line = list(map(int, input().split()))
cnt = {}
for i in range(n):x = line[i]if x in cnt:cnt[x] += 1else:cnt[x] = 1
a = 0
b = 0
for y in cnt.values():if y == 1:a += 1elif y > 2:b += y - 2
if b >= a:print(b)
else:print((a - b) // 2 + b)