班級活動

問題描述

小明的老師準備組織一次班級活動。班上一共有?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代碼