蓝桥杯14届国赛 班级活动

问题描述

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

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

输入格式

输入共 2 行。

第一行为一个正整数 n。

第二行为 n 个由空格隔开的整数 a1,a2,...,an​。

输出格式

输出共 1 行，一个整数。

样例输入

4
1 2 2 3

样例输出

1

样例说明

仅需要把 a1​ 改为 3 或者把 a3​ 改为 1 即可。

评测用例规模与约定

对于 20% 的数据，保证 n≤。

对于 100% 的数据，保证 n≤。

 

 统计一下每个id的人数：

①如果id的人数为2，不用改

②如果id的人数>2，说明多出的2的部分要改 优先改成id人数为1的id，这样就能保证修改一次，就能出现合法配对的情况

如果还有余下的，所有余下的都要改

③如果id的人数<2（id的人数为1），暂时不用改，因为要求最小操作次数，应该有其他人来改为当前id，从而和这个人配对

如果还有余下的，只需要改余下的一半

设id的人数<2的人数为A  ， id的人数>2的人数为B，有两种情况：

①B>=A，修改的次数为B

1 2 2 2 2 3 2 2  → 1 2 2 1 3 3 4 4

②B<A，修改的次数为B+(A-B)/2

1 2 2 2 2 3 4 5  → 1 2 2 1 3 3 4 4

#include<iostream>
using namespace std;const int N = 1e5+10;
int n;
int a[N]; 
int cnt[N];int cnt1, cnt2;
int ans;int main()
{cin>>n;for(int i=1; i<=n; ++i){cin>>a[i];cnt[a[i]]++;}for(int i=1; i<=n; ++i){if(cnt[i]==1) cnt1++;if(cnt[i]>2) cnt2 += cnt[i]-2;}if(cnt2 >= cnt1) ans = cnt2;else ans = cnt2 + (cnt1-cnt2)/2;cout<<ans;return 0;
}