当前位置：首页 > article >正文

蓝桥杯P17153-班级活动题解

article 2025/3/13 14:23:23

题目：班级活动

题目来源：蓝桥云课 - 班级活动

题目描述

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

输入格式：

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

输出格式：

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

样例输入：

 6
 1 2 2 3 3 3

样例输出：

解题思路

目标：使序列中每个数字的出现次数都变成偶数（即每种数字都能配成对）。
统计频率：用一个数组 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) { // 如果某个数字出现次数超过 2
             up += (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