P9421-蓝桥杯-2023-国-B-班级活动-数学题配对问题
目录
P9421 [蓝桥杯 2023 国 B] 班级活动–数学题（配对问题）
题目
解析
题目中的配对问题，要求配对的成功的数字不重复，那么我们需要把多余2次的数记录下来，我们巧妙的运用到了哈希方法。
开始分析解题思路。一共有3种情况，
1.如果配对次数为1的值，我们只需要更改一次
2.如果配对次数大于2的值，我们需要更改两次
3.让次数大于2的值和次数为1的值配对，也只需更改一次
题目中说到最少，那我们肯定选更改一次的。那我们优先选次数大于2的和次数为1的值进行配对，如果次数为1的值用完那就只能用情况2了将剩余的次数*2
for (int i = 1; i <= n; i++) {
cin >> a;
f[a]++;//这里听挺巧秒的，记一下
if (f[a] > 2)
res++;//记录多出来的次数
巧思
这里巧妙的运用到哈希用res记录了大于2的次数一共有多少
f[a]++;
if (f[a] > 2)
res++;代码
#include <iostream>
#include <vector>
#include <set>
#include <cstring>
#include <algorithm>
#include <math.h>
#include <queue>
#include <climits> // 包含INT_MAX常量
#include <cctype>
using namespace std;
int n, a, cnt, res;
int f[100010];
int main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a;
f[a]++;//这里听挺巧秒的，记一下
if (f[a] > 2)
res++;
}
for (int i = 1; i <= n; i++) {
if (f[i] == 1)
cnt++;
}
if(cnt>res) cout<<res+(cnt-res)/2;
else
cout <<res;
return 0;
}