PKU 2952 Election
http://poj.org/problem?id=2952
選挙のシミュレーション。
g個のグループにはそれぞれm_i人の投票者がいて、グループ内の人は立候補者に対して同じ優先順位を持っている。
このとき、各グループ内でもっとも優先順位の高い人がそのグループ人数分の票をもらう。そして、票が最も少ない人が落選して、優先順位のリストから抜ける。
これを候補者がひとりになるまで繰り返す。
サンプルで説明するなら。
10 1 4 2 3
15 3 2 1 4
12 4 3 2 1
ここで2の人は0票しか獲得出来ていないので、候補から外される。
10 1 4 3
15 3 1 4
12 4 3 1
今度は、1の人が最小(10)なので、
10 4 3
15 3 4
12 4 3
3が15票で最小なので
10 4
15 4
12 4
となり4が残る。
この問題のことではないですが、選挙のシミュレーションの問題って問題の意味が読み取れないとサンプルすら出てこないことがあって難しいことがありますよね。
ソースコードがかなりきたなくなりました。
main(){ int g,n; while(cin>>g>>n,g|n){ vector<int> pre[g]; int m[g]; rep(i,g){ cin>>m[i]; int t; rep(j,n){ int t; cin>>t; pre[i].pb(t); } } set<int> left; rep(i,n)left.insert(i+1); rep(i,n-1){ int vo[n]; memset(vo,0,sizeof(vo)); rep(j,g)vo[pre[j][0]-1]+=m[j]; int minv=10000,mine=0; rep(j,n){ if(left.count(j+1) && vo[j]<=minv)mine=j,minv=vo[j]; } left.erase(mine+1); rep(i,g){ FOR(iter,pre[i]){ if(*iter==mine+1){ pre[i].erase(iter); break; } } } } cout<<pre[0][0]<<endl; } }