PKU 3312 Mahershalalhashbaz, Nebuchadnezzar, and Billy Bob Benjamin Go to the Regionals
http://poj.org/problem?id=3312
n人の名前が与えられる。このn人をk人のチームに分けたい(ただし、kはnを割り切れる)
このとき、チームに含まれる人の名前はそのチーム内の名前の長さの平均から2以上差が出ないようにしたい。与えられた名前のリストでそのようなチーム分けが可能かどうかを判定しろというような問題。
名前の長さでソートして小さい順にまとめていく。
それでできなければ無理。
int in[1000]; main(){ int n,k; int ca=0; while(cin>>n>>k,n|k){ ++ca; cout<<"Case "<<ca<<": "; rep(i,n){ string ss; cin>>ss; in[i]=SZ(ss); } sort(in,in+n); bool ok=true; rep(i,n/k){ int sum=0; rep(j,k){ sum+=in[i*k+j]; } if((in[i*k]+2)*k<sum || sum<(in[i*k+k-1]-2)*k){ ok=false; break; } } if(ok)cout<<"yes"<<endl; else cout<<"no"<<endl; cout<<endl; } }