第十四届蓝桥杯大赛软件赛决赛 C/C++ 大学 B 组试题 C: 班级活动 - 服务器托管|北京服务器租用|机房托管租用|IDC托管租用|机房机柜带宽租用-价格及费用咨询

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

【问题描述】

小明的老师准备组织一次班级活动。班上一共有

$n$ 名（

$n$ 为偶数）同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个

$n$ 以内的正整数作为 id，第

$i$ 名同学的 id 为

a_i

$a_{i}$ 。

老师希望通过更改若干名同学的 id 使得对于任意一名同学

$i$ ，有且仅有另一名同学

$j$ 的 id 与其相同（

a_i = a_j

$a_{i} = a_{j 服务器托管网}$ ）。请问老师最少需要更改多少名同学的 id？

【输入格式】

输入共

2
服务器托管网

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

$n$ 。
第二行为

$n$ 个由空格隔开的整数

⋯

a_1, a_2, cdots, a_n

$a_{1}, a_{2}, \dots, a_{n}$ 。

【输出格式】

输出共

$1$ 行，一个整数。

【样例输入】

4
1 2 2 3

【样例输出】

【样例说明】

仅需要把

a_1

$a_{1}$ 改为

$3$ 或者把

a_4

$a_{4}$ 改为

$1$ 即可。

评测用例规模与约定

对于 $10^3 n≤103。$
对于 $10^5 n≤105。$

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

1. 刚好有两个学号相同

这种情况不做改变即可符合题意。

2. 有大于两个学号相同

这种情况需要将多的改变为其他学号。

3. 只有一个学号

这种情况需要有多的学号转化成该学号或把该学号转化成另一个只有一个的学号。
那么，他们对答案的贡献分别是：
情况 1：无。
情况 2：ans ← sum1 − 2
情况 3：sum1 + ( sum2 – sum1 ) / 2

#include 
using namespace std;

const int N = 1e5 + 10;
int a[N],cnt[N];

int main() 
{
	int n;cin>>n;
	for(int i=1;in;i++) 
	{
		cin>>a[i];
		cnt[a[i]]++;
	}
	int sum1=0,sum2=0;
	for(int i=1;i100000;i++)
	{
		if(cnt[i]>=2) sum1+=(cnt[i]-2);
		else sum2+=cnt[i];
	}
	if(sum1>sum2) coutsum1;
	else coutsum1+(sum2-sum1)/2;
	return 0;
}

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 自然语言处理 Paddle NLP – 快递单信息抽取 (ERNIE 1.0)

文档检索：需要把业务问题拆解成子任务。文本分类 -> 文本匹配 -> 等任务 -> Panddle API 完成子任务 -> 子任务再拼起来介绍在2017年之前，工业界和学术界对文本处理依赖于序列模型Recurrent Neural…