蓝桥杯P17153-班级运动 题解

题目：班级运动

题目来源：蓝桥云课 - 班级运动
题目形貌

给定一个包含多少整数的序列（个数为偶数），需要通过调整将所有数字配成一对一对的形式。每次操作可以将一个数字改为任意其他数字，问最少需要修改多少个数字才气使每个数字的出现次数均为偶数。
输入格式：

• 第一行输入一个整数 n（偶数），表现序列中数字的个数。
  
• 第二行输入 n 个整数，表现序列中的数字。
  

输特别式：

• 输出一个整数，表现最少需要修改的数字个数。
  

样例输入：

1.  6
2.  1 2 2 3 3 3

复制代码

样例输出：

1. 1

复制代码

---

解题思绪

• 目标：使序列中每个数字的出现次数都变成偶数（即每种数字都能配成对）。
  
• 统计频率：用一个数组 arr[] 统计每个数字出现的次数。
  
• 分析调整：
  
  
  
  • 如果某个数字出现次数大于 2 的部分（多于 1 对的部分），可以将其“多余”的数字改成其他数字，记为 up。
    
  • 如果某个数字只出现 1 次（无法配对），需要再引入一个雷同的数字或将其改成其他已有数字，记为 down。
    
  
  
• 盘算最小修改次数：
  
  
  
  • up 表现可以“腾出”的多余数字个数。
    
  • down 表现需要“补齐”的单个数。
    
  • 根据 up 和 down 的大小关系：
    
    
    
    • 如果 up > down，说明多余的数字足够补齐所有落单的数字，终极修改次数为 up。
      
    • 如果 down > up，说明多余的数字不够，还需要额外配对，剩余的落单数字需要两两配对，终极修改次数为 up + (down - up) / 2。
      
    
    
  
  

---

代码实现与注释

1.  #include<iostream>
2.  #include<vector>
3.  using namespace std;
4.  ​
5.  /*
6.  变量说明：
7.  - n：输入的数字个数（偶数）
8.  - temp：临时变量，存储输入的每个数字
9.  - up：大于一对（出现次数 > 2）的数字中多余的个数总和
10.  - down：出现次数等于 1 的数字个数（落单的数字）
11.  - ff：最终输出的最小修改次数
12.  - arr[]：哈希数组，记录每个数字出现的次数
13.  */
14.  int n, temp, up, down, ff;
15.  int arr[100001] = { 0 }; // 初始化为 0，范围根据题目约束设置
16.  ​
17.  int main() {
18.      ios::sync_with_stdio(0); // 加速输入输出
19.      cin.tie(0); cout.tie(0);
20.  ​
21.      // 输入部分
22.      cin >> n; // 输入数字个数
23.      while (n--) { // 输入 n 个数字
24.          cin >> temp;
25.          arr[temp]++; // 统计每个数字的出现次数
26.      }
27.  ​
28.      // 统计可调整的数字个数
29.      for (int i = 0; i <= 100001; i++) { // 遍历所有可能出现的数字
30.          if (arr[i] > 2) { // 如果某个数字出现次数超过 2
31.              up += (arr[i] - 2); // 多余的个数可以用来调整
32.          } else if (arr[i] == 1) { // 如果某个数字只出现 1 次
33.              down++; // 记录需要补齐的落单数字个数
34.          }
35.      }
36.  ​
37.      // 计算最小修改次数
38.      if (up > down) { // 多余的数字足够补齐所有落单数字
39.          ff = up; // 修改次数取决于多余的数字
40.      } else if (down > up) { // 多余数字不够，剩余落单数字需两两配对
41.          ff = (down - up) / 2 + up; // up 用于补齐部分，(down - up) / 2 用于两两配对
42.      } else { // up == down，多余数字恰好补齐落单数字
43.          ff = up; // 修改次数等于 up
44.      }
45.  ​
46.      // 输出结果
47.      cout << ff << endl;
48.      return 0;
49.  }

复制代码

---

代码运行过程（以样例为例）

输入：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)，用于存储频率数组。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。