問題描述

小明的老師準備組織一次班級活動。班上一共有?n?名 (n?為偶數) 同學，老師想把所有的同學進行分組，每兩名同學一組。為了公平，老師給每名同學隨機分配了一個?n?以內的正整數作為?id，第?i?名同學的?id?為?ai?。

老師希望通過更改若干名同學的?idid?使得對于任意一名同學?i，有且僅有另一名同學?j的?id?與其相同 (ai=aj?)。請問老師最少需要更改多少名同學的?id？

輸入格式

輸入共?2?行。

第一行為一個正整數?n。

第二行為?n?個由空格隔開的整數?a1,a2,...,an。

輸出格式

輸出共?1?行，一個整數。

樣例輸入

4
1 2 2 3

樣例輸出

1

樣例說明

僅需要把?a1??改為?3?或者把?a3??改為?1?即可。

思路：?

利用 map來判斷，如果id出現次數不為2，就需要修改，統計出現次數為1次(t1)和大于2次（t2）的，如果t1>=t2，每個t2都可以和一個t1對應改變，否則的話多余的t2都需要改變。

代碼：

#include <bits/stdc++.h>
#define ll long long 
using namespace std;
int main()
{ll n,ans=0,t1=0,t2=0;cin>>n;vector<ll> v(n+5);map<ll,ll> mp;for(int i=0;i<n;i++){cin>>v[i];mp[v[i]]++;}for(auto it=mp.begin();it!=mp.end();it++){if(it->second!=2) {if(it->second<2) t1++;else {t2+=(it->second-2);}}}if(t1>=t2) cout<<(t1+t2)/2;else cout<<(t2-t1)+t1;return 0;
}