Codeforces #377 Div2 E. Sockets

意外とTLEが多かったみたいね。
http://codeforces.com/contest/732/problem/E

問題

N個のコンピュータがあり、それぞれ必要な電力はA[i]である。
またM個のコンセントがあり、電力の出力はB[j]である。

各コンセントには、出力と必要な電力が一致するコンピュータを１台だけつなげることができる。
ここでコンセントにアダプタを挿すと、出力が半分(小数点以下切り上げ)となる。
アダプタは任意の数を挿すことができる。

適切なコンピュータとコンセントの割り当てを行うと、最大何個コンピュータをつなげられるか。
またその時のアダプタ数とつなぎ方を答えよ。

解法

B[j]の小さい順に処理し、つなぐコンピュータを探す。
これは単純に電力が一致するコンピュータが見つかるまで、アダプタを１つずつ増やしてみていけば良い。

int N,M;
pair<int,int> S[202020];

int C,U;
int A[202020],B[202020];
map<int,vector<int>> MP;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,N) {
		cin>>x;
		MP[x].push_back(i);
	}
	
	FOR(i,M) {
		cin>>x;
		S[i]={x,i};
	}
	sort(S,S+M);
	FOR(i,M) {
		x = S[i].first;
		j =0;
		while(x) {
			if(MP.count(x)) {
				y = MP[x].back();
				A[S[i].second]=j;
				B[y]=S[i].second+1;
				MP[x].pop_back();
				if(MP[x].empty()) MP.erase(x);
				C++;
				U+=j;
				break;
			}
			if(x==1) break;
			j++;
			x=x/2+x%2;
		}
	}
	
	_P("%d %d\n",C,U);
	FOR(i,M) _P("%d%c",A[i],(i==M-1)?'\n':' ');
	FOR(i,N) _P("%d%c",B[i],(i==N-1)?'\n':' ');
	
}

まとめ

これはすぐ思いつけた。