Codeforces #217 Div2. C. Mittens

CF217はDiv2 Onlyだけど練習で参加。
A～Cはさっくり通せたけど、Dで時間をかけすぎて終了。
Dを落とした人が多かったのでそこそこの順位だけど、Dが解けないのは不満。
その後何とかEditorialを見ずD・Eも通しました。
http://codeforces.com/contest/370/problem/C

問題

N人の人がそれぞれ両手お揃いの色の手袋をしており、その色はC[i]である。
互いに手袋を交換しあい、両手の手袋の色が異なるようにしたい。

両手の色が別々になっている人の最大人数は何人か。
また、その時の手袋の組み合わせ例を示せ。

解法

手袋の数を色ごとに集計し、少ない順にソートする。
その数列をPとした場合、C[P[0]]、C[P[1]]、C[P[2]]…の順で数が少ない。
この時、左手はC[P[0]]から順に一つずつ取っていって各人C[P[1]]、C[P[2]]、…ととっていく。
右手は最大の数であるC[P[N-1]]から先にとって、その後C[P[0]]からとっていけばよい。
下記コードでは左手をV、右手をV2から処理している。

左手と右手はC[P[N-1]]の個数以上ずれたものを取るので、C[P[N-1]]以外の色が左右で重複することはない。
C[P[N-1]]の手袋が全体の半分以上あると、左右C[P[N-1]]の人が現れるので注意。

int N,M;
int C[101];
vector<pair<int,int> > V,V2;

void solve() {
	int f,i,j,k,l,x,y,ma=0;
	
	cin>>N>>M;
	FOR(x,N) {
		cin>>y;
		C[y-1]++;
	}
	FOR(i,M) if(C[i]) V.push_back(make_pair(C[i],i));
	sort(V.begin(),V.end());
	V2=V;
	for(i=V2.size()-1;i>=1;i--) swap(V2[i],V2[i-1]);
	
	_P("%d\n",min(N,2*N-2*V2[0].first));
	x=y=0;
	FOR(i,N) {
		_P("%d %d\n",V[x].second+1,V2[y].second+1);
		if(--V[x].first==0) x++;
		if(--V2[y].first==0) y++;
	}
}

まとめ

これはすんなり解けてよかった。