[蓝桥杯 2023 国 B] 班级活动

[蓝桥杯 2023 国 B] 班级活动

题目描述

小明的老师准备组织一次班级活动。班上一共有 $n$ 名（$n$ 为偶数）同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 $n$ 以内的正整数作为 id，第 $i$ 名同学的 id 为 $a_i$。

老师希望通过更改若干名同学的 id 使得对于任意一名同学 $i$，有且仅有另一名同学 $j$ 的 id 与其相同（$a_i=a_j$）。请问老师最少需要更改多少名同学的 id？

输入格式

输入共 $2$ 行。

第一行为一个正整数 $n$。

第二行为 $n$ 个由空格隔开的整数 $a_1,a_2,\cdots ,a_n$。

输出格式

输出共 $1$ 行，一个整数。

样例 #1

样例输入 #1

4
1 2 2 3

样例输出 #1

1

提示

样例说明

仅需要把 $a_1$ 改为 $3$ 或者把 $a_4$ 改为 $1$ 即可。

评测用例规模与约定

• 对于 $20\%$ 的数据，保证 $n\le 10^3$。
• 对于 $100\%$ 的数据，保证 $n\le 10^5$。

第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组 C 题**

1：题意
给定一个数列，求最少变化多少个数可以使每个数有且只有一个数和他相等。

2：由题目可以想到，我们可以将数列中的数大致分为三种：

• 刚好有两个学号相同 这种情况不做改变即可符合题意。
• 有大于两个学号相同 这种情况需要将多的改变为其他学号。
• 只有一个学号 这种情况需要有多的学号转化成该学号或把该学号转化成另一个只有一个的学号。

#include <iostream>
using namespace std;
#include <bits/stdc++.h>

int n;
const int N=1e5+10;
int t[N];
int m;
int d,ss,ans;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	 {
	 	 cin>>m;
	 	 ++t[m];//创造一个桶，用来存放序号有多少个
	 }
	 
	 for(int i=1;i<=n;i++)
	 {
	 	if(t[i]==1)//出现1次的序号
	 	{
	 		d+=t[i];//总和
		 }
		 else  if(t[i]>2)//出现次数两次以上的序号
		 {
		 	ss+=t[i]-2;//结果是出现次数减去2（可以变换的次数）
		 }
	 }
	 if(d>=ss)//出现1次的序号多
	 {
	 	ans=(d-ss)/2+ss;
	 }
	 else if(ss>d) //两个的多
{
		 ans=(ss-d)+d;
}
	 cout<<ans;
	 


	return 0;
}