蓝桥杯 15g

班级活动

问题描述

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

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

输入格式

输入共 22 行。

第一行为一个正整数 nn。

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

输出格式

输出共 1 行，一个整数。

注意：

题意很明确就是根据相同的id两两一组，但是 每个id 只能找到一个与之相同的！ 如果出现三次2，就有一个需要改变编号。

除了刚好出现两次的数字， 就是出现1次，出现n次的，根据这个思路写

代码（60%）

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5+10;
#define int long long
int num[N];signed main()
{// 请在此输入您的代码int n;cin >> n;int a[N];for(int i = 0; i < n; i ++ ){cin >> a[i];}int ans  = 0;  for(int i = 0; i < n; i ++ ){if(num[a[i]] == -1) {ans ++;}if(num[a[i]] > -1) num[a[i]]++;if(num[a[i]] == 2) {num[a[i]] = -1;}}for(int i = 0; i < n; i ++ ){if(num[a[i]] == 1) ans ++;}cout << ans/2;return 0;
}

出现问题：

上述代码是将所有出现一次以及出现n次的数量相加再除以二

只考虑了修改次数，但没有考虑到题目要求最小值！

最小值如何求？

首先肯定是从n个和1个里面想怎么改，n个是一定要全部改的因为只要求出现一个相同id，那么n个如何改？尽量向只有1个靠拢，这样1个里面的就凑成两个不用改了。

然后就考虑n个和1个的数量多少问题。

n个>1个：改n

n个 < 1个：（1个的 - n个的）之后，剩下都是1个，没必要全都改，只用改除/2。

至于（1 - n）则全部都要改。

ac代码

#include <iostream>
#include <algorithm>
using namespace std;const int N = 1e5+10;
#define int long long
int num[N];signed main()
{// 请在此输入您的代码int n;cin >> n;int a[N];for(int i = 0; i < n; i ++ ){cin >> a[i];num[a[i]] ++;}int ans  = 0;  int numn = 0;int num1 = 0;for(int i = 0; i <= n; i ++ ){if(num[i] > 2) {numn += num[i]-2 ;}if(num[i] == 1) {num1 ++;}}if(numn >= num1) ans = numn;else{ans = (num1-numn)/2 + numn;}cout << ans;return 0;
}