PKU 3646 The Dragon of Loowater
http://poj.org/problem?id=3646
ドラゴンの首の高さと、騎士の背の高さが入力される。
このとき、すべてのドラゴンの首に対して、それより高い騎士を用意し、かつその背の合計を最小にしろというような問題。
mapを使ってちょちょいとやる。
int in[20000]; main(){ int n,m; while(cin>>n>>m,n|m){ map<int,int> kn; rep(i,n)cin>>in[i]; sort(in,in+n); rep(i,m){ int t; cin>>t; ++kn[t]; } int ans=0; rep(i,n){ map<int,int>::iterator p=kn.lower_bound(in[i]); if(p==kn.end()){ ans=-1; break; } ans+=p->F; p->S--; if(p->S==0)kn.erase(p); } if(ans>=0)cout<<ans<<endl; else cout<<"Loowater is doomed!"<<endl; } }