蓝桥杯班级活动

题目描述

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

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

输入格式

输入共 2行。第一行为一个正整数 n。第二行为 nn 个由空格隔开的整数 a1,a2,...,ana1​,a2​,...,an​。

输出格式

输出共 1 行，一个整数。

输入样例： 4 1 2 2 3 输出样例： 1

 思路：

题目要求有且仅有两个数相同，因此，我们要分别记录只出现一次的数和出现超过两次的数，如果只有出现一次的数，且其个数为c1,那么需要修改c1/2;如果只有出现超过两次的数，且其个数为c2，那么修改次数为c2，显然可以发现，修改只出现一次的数会更简单；那么如果c1,c2同时存在时，当c2>=c1,则要修改c1+(c2-c1)=c2次，反之，则要修改c2+(c1-c2)/2次

#include<bits/stdc++.h> using namespace std; #define int long long const int N = 1e6; int n,C=0,c1=0,c2=0; int c[N],a[N]; bool v[N]; signed main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; for(int i=0;i<n;i++) { cin>>a[i]; c[a[i]]++; } for(int i=0;i<n;i++) { if(c[a[i]]>2&&!v[a[i]]) { c2+=c[a[i]]-2; v[c2]=true; } if(c[a[i]]==1) c1++; } if(c1>=c2) C=c2+(c1-c2)/2; if(c2>c1) C=c2; cout<<C<<endl; return 0; }

细节：为了避免重复计算，所以当一个数出现次数大于等于两次时需要做标记。