Codeforces #180 Div1. B. Fish Weight

今回はコード量が少な目だね。
http://codeforces.com/contest/297/problem/B

問題

池にK種類の魚がいる。それぞれの重さW[1]～W[K]は単調増加になっている。
ここで、AliceとBobが釣った魚の番号一覧が与えられる。
このとき、Aliceの釣った魚の総重量がBobより多くなるようなW[1]～W[K]が存在するか答えよ。

問題

魚番号を大きい順にAliceとBobの所有数を累積していく。
もし途中でAliceの方が累積数が多くなった魚番号をiとすると、W[i]～W[K]を無限大に大きくし、W[1]～W[i-1]が小さいと仮定するとAliceの総重量が勝る。

よって、累積数が多くなる魚番号を順に数えればよい。
Kは10^9までと大きいので、以下ではmapを使って登場した魚番号のみカウントしている。

int N,M,K;
map<int,int> MM;

void solve() {
	int f,r,i,j,k,l,x,y;
	
	cin>>N>>M>>K;
	FOR(i,N) MM[-GETi()]++;
	FOR(i,M) MM[-GETi()]--;
	
	j=0;
	for(map<int,int>::iterator mit=MM.begin();mit!=MM.end();mit++) {
		if(mit->second>j) {
			_P("YES\n");
			return;
		}
		j-=mit->second;
	}
	
	_P("NO\n");
	return;
}

まとめ

一見問題がややこしいけど、コードはシンプルだね。