题目描述
小明的老师准备组织一次班级活动。班上一共有 ( n ) 名（( n ) 为偶数）同学，老师想把所有的同学进行分组，每两名同学一组。为了公平，老师给每名同学随机分配了一个 ( n ) 以内的正整数作为 id，第 ( i ) 名同学的 id 为 ( a_i )。
老师希望通过更改若干名同学的 id 使得对于任意一名同学 ( i )，有且仅有另一名同学 ( j ) 的 id 与其相同（( a_i = a_j )）。请问老师最少需要更改多少名同学的 id？
输入格式
输入共 2 行。
第一行为一个正整数 ( n )。
第二行为 ( n ) 个由空格隔开的整数 ( a_1, a_2, ..., a_n )。
输出格式
输出共 1 行，一个整数。
输入输出样例
输入 #1
4
1 2 2 3
输出 #1
1
说明/提示
样例说明
仅需要把 ( a_1 ) 改为 3 或者把 ( a_4 ) 改为 1 即可。
评测用例规模与约定
- 对于 20% 的数据，保证 ( n <= 10^3 )。
- 对于 100% 的数据，保证 ( n <= 10^5 )。
题解:
一共有两种情况
- 只出现过一次的id个数 cnt1 >= 出现过2次以上的id个数 cnt2。 此时把 所有cnt2 都更改成一个id只出现过一次的, 再加上剩下的 cnt1 / 2
- 只出现过一次的id个数 cnt1 < 出现过2次以上的id个数 cnt2。 此时把 cnt1个cnt2 都改成一个id只出现过一次的, 再加上剩下的 cnt2 /2
ps: 说白了就是 当有cnt1的时候, 尽可能把cnt2变成cnt1, 当cnt2有剩余的话, 还需要改变 "剩余的cnt2的个数" 次, 当cnt1有剩余的话, 还需要改变 "剩余的cnt1的个数 / 2"
ac代码
标签：同学,班级,int,个数,蓝桥,cnt2,cnt1,活动,id From： https://www.cnblogs.com/xxctx/p/18207063