题目：班级活动
题目来源：蓝桥云课 - 班级活动
题目描述
给定一个包含若干整数的序列（个数为偶数），需要通过调整将所有数字配成一对一对的形式。每次操作可以将一个数字改为任意其他数字，问最少需要修改多少个数字才能使每个数字的出现次数均为偶数。
输入格式：
-
第一行输入一个整数
n（偶数），表示序列中数字的个数。 -
第二行输入
n个整数，表示序列中的数字。
输出格式：
-
输出一个整数，表示最少需要修改的数字个数。
样例输入：
61 2 2 3 3 3样例输出：
1解题思路
-
目标：使序列中每个数字的出现次数都变成偶数（即每种数字都能配成对）。
-
统计频率：用一个数组
arr[]统计每个数字出现的次数。 -
分析调整：
-
如果某个数字出现次数大于 2 的部分（多于 1 对的部分），可以将其“多余”的数字改成其他数字，记为
up。 -
如果某个数字只出现 1 次（无法配对），需要再引入一个相同的数字或将其改成其他已有数字，记为
down。
-
-
计算最小修改次数：
-
up表示可以“腾出”的多余数字个数。 -
down表示需要“补齐”的单个数。 -
根据
up和down的大小关系：-
如果
up > down，说明多余的数字足够补齐所有落单的数字，最终修改次数为up。 -
如果
down > up，说明多余的数字不够，还需要额外配对，剩余的落单数字需要两两配对，最终修改次数为up + (down - up) / 2。
-
-
代码实现与注释
#include<iostream> #include<vector>using namespace std;/*变量说明：- n：输入的数字个数（偶数）- temp：临时变量，存储输入的每个数字- up：大于一对（出现次数 > 2）的数字中多余的个数总和- down：出现次数等于 1 的数字个数（落单的数字）- ff：最终输出的最小修改次数- arr[]：哈希数组，记录每个数字出现的次数*/int n, temp, up, down, ff;int arr[100001] = { 0 }; // 初始化为 0，范围根据题目约束设置int main() {ios::sync_with_stdio(0); // 加速输入输出cin.tie(0); cout.tie(0);// 输入部分cin >> n; // 输入数字个数while (n--) { // 输入 n 个数字cin >> temp;arr[temp]++; // 统计每个数字的出现次数}// 统计可调整的数字个数for (int i = 0; i <= 100001; i++) { // 遍历所有可能出现的数字if (arr[i] > 2) { // 如果某个数字出现次数超过 2up += (arr[i] - 2); // 多余的个数可以用来调整} else if (arr[i] == 1) { // 如果某个数字只出现 1 次down++; // 记录需要补齐的落单数字个数}}// 计算最小修改次数if (up > down) { // 多余的数字足够补齐所有落单数字ff = up; // 修改次数取决于多余的数字} else if (down > up) { // 多余数字不够，剩余落单数字需两两配对ff = (down - up) / 2 + up; // up 用于补齐部分，(down - up) / 2 用于两两配对} else { // up == down，多余数字恰好补齐落单数字ff = up; // 修改次数等于 up}// 输出结果cout << ff << endl;return 0;}代码运行过程（以样例为例）
输入：6 1 2 2 3 3 3
-
统计频率：
-
arr[1] = 1 -
arr[2] = 2 -
arr[3] = 3
-
-
计算
up和down：-
arr[1] = 1，down = 1 -
arr[2] = 2，无需调整 -
arr[3] = 3，up = 3 - 2 = 1 -
结果：
up = 1，down = 1
-
-
计算修改次数：
-
up == down，ff = up = 1
-
-
输出：
1
解释：数字 3 出现 3 次，多余的 1 个可以改为 1，使 1 和 3 的出现次数都变为偶数（1:2次，2:2次，3:2次），只需修改 1 个数字。
注意事项
-
边界条件：题目假设输入的数字范围在
[0, 100000]内，因此arr数组大小设为100001。 -
时间复杂度：
O(n + k)，其中n是输入数字个数，k是数字范围（这里为 100001）。 -
空间复杂度：
O(k)，用于存储频率数组。