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

P9421 [蓝桥杯 2023 国 B] 班级活动--数学题（配对问题）

article 2025/3/11 4:14:37

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;
}