PKU 1323 Game Prediction
http://poj.org/problem?id=1323
自分を含むm人の人が、それぞれn枚のカードを持っている。それぞれのカードには1〜n*mの数字が重複なく書かれている。このゲームの1回の試行では、m人の人がそれぞれ1枚ずつカードを場に出し、一番数字の高かった人が勝つ。
今自分のもち札が分かっているとき、自分が最低何回勝てるかを答えるという問題。
自分が今持っているカードより大きい最小のカードを他の人が持っていれば、その人はそのカードをだし、残りの人は小さいものから出していくと考えると、うまくいきました。
main(){ int n,m; int ca=0; while(cin>>m>>n,n|m){ ++ca; set<int> my,en; rep(i,n){ int t; cin>>t; my.insert(t); } rep(i,m*n){ if(my.count(i+1))continue; en.insert(i+1); } int ans=n; rep(i,n){ int myt=*my.begin(); my.erase(myt); bool ok=0; FOR(siter,en){ if(*siter>myt){ int ent=*siter; --ans; bool inclu=false; rep(i,m-2){ int t=*en.begin(); if(t==ent)inclu=true; en.erase(t); } if(inclu)en.erase(*en.begin()); else en.erase(ent); ok=1; break; } } if(ok)continue; rep(i,m-1)en.erase(*en.begin()); } cout<<"Case "<<ca<<": "<<ans<<endl; } }