做策划的网站推广,重庆seo排名公司,永久免费手机网站自助建站,wordpress权重[蓝桥杯 2023 国 B] 班级活动
【问题描述】
小明的老师准备组织一次班级活动。班上一共有 n n n 名#xff08; n n n 为偶数#xff09;同学#xff0c;老师想把所有的同学进行分组#xff0c;每两名同学一组。为了公平#xff0c;老师给每名同学随机分配了一个 n n …[蓝桥杯 2023 国 B] 班级活动
【问题描述】
小明的老师准备组织一次班级活动。班上一共有 n n n 名 n n n 为偶数同学老师想把所有的同学进行分组每两名同学一组。为了公平老师给每名同学随机分配了一个 n n n 以内的正整数作为 id第 i i i 名同学的 id 为 a i a_i ai。
老师希望通过更改若干名同学的 id 使得对于任意一名同学 i i i有且仅有另一名同学 j j j 的 id 与其相同 a i a j a_i a_j aiaj。请问老师最少需要更改多少名同学的 id
【输入格式】
输入共 2 2 2 行。 第一行为一个正整数 n n n。 第二行为 n n n 个由空格隔开的整数 a 1 , a 2 , ⋯ , a n a_1, a_2, \cdots, a_n a1,a2,⋯,an。
【输出格式】
输出共 1 1 1 行一个整数。
【样例输入】
4
1 2 2 3【样例输出】
1【样例说明】
仅需要把 a 1 a_1 a1 改为 3 3 3 或者把 a 4 a_4 a4 改为 1 1 1 即可。
评测用例规模与约定
对于 20 % 20\% 20% 的数据保证 n ≤ 1 0 3 n \le 10^3 n≤103。对于 100 % 100\% 100% 的数据保证 n ≤ 1 0 5 n \le 10^5 n≤105。
由题目可以想到我们可以将数列中的数大致分为三种
1. 刚好有两个学号相同
这种情况不做改变即可符合题意。
2. 有大于两个学号相同
这种情况需要将多的改变为其他学号。
3. 只有一个学号
这种情况需要有多的学号转化成该学号或把该学号转化成另一个只有一个的学号。 那么他们对答案的贡献分别是 情况 1无。 情况 2ans ← sum1 − 2 情况 3sum1 ( sum2 - sum1 ) / 2
#include bits/stdc.h
using namespace std;const int N 1e5 10;
int a[N],cnt[N];int main()
{int n;cinn;for(int i1;in;i) {cina[i];cnt[a[i]];}int sum10,sum20;for(int i1;i100000;i){if(cnt[i]2) sum1(cnt[i]-2);else sum2cnt[i];}if(sum1sum2) coutsum1;else coutsum1(sum2-sum1)/2;return 0;
}
