PKU 3646 The Dragon of Loowater

問題

二つの数列a[i]およびb[i]が与えられる。
b[i]から数列c[i]を選び（一つの項は高々一回までしか選ぶことができない）、
すべてのiについてa[i]≦c[i]となるようにしたい。

このときΣc[i]の最小値を求めよ。

制約条件

n≦20000

方針

a[i]を小さい順にソートする。
a[i]に対して、貪欲にまだ使ってないb[i]の最小値を割り当てればよい。

multisetを使ったらTLE.
map<int, int>を使ったら320msで通った。PKUのmultisetしょぼすぎる。

ソースコード

int n, m, h[200000];

int main()
{
	while(scanf("%d%d", &n, &m), n || m){
		rep(i, n) scanf("%d", h + i);
		sort(h, h + n);
		map<int, int> s;
		rep(i, m){
			int t;
			scanf("%d", &t);
			s[t]++;
		}
		ll ans = 0;
		rep(i, n){
			map<int, int>::iterator it = s.lower_bound(h[i]);
			if(it == s.end()){
				puts("Loowater is doomed!"); goto END;
			}
			ans += it->first;
			if(--it->second == 0) s.erase(it);
		}
		printf("%lld\n", ans);
		END:;
	}
	return 0;
}