C++にPerlやPython並に使いやすいtupleが欲しい。
http://yukicoder.me/problems/no/433
問題
N個のチームが大会を行った。
i番のチームはS[i]問の問題を解き、ペナルティはP[i]で、U[i]大学出身である。
以下の順でチームをK個まで選ぶとき、どのチームが選択されるか。
- 未選抜のチーム中解いた問題数が最大のチーム
- ↑も同着のチームが複数ある場合、今までに選抜された同じ大学のチーム数が最小のチーム
- ↑が同着のチームが複数ある場合、そのうちペナルティが最小のチーム
解法
priority_queueで(S[x],-学内順位,-P[x])の大きい順に選択していけば良い。
int N,K; int S[101010]; int P[101010]; int U[101010]; vector<pair<pair<int,int>,int>> E[101010]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; FOR(i,N) { cin>>S[i]>>P[i]>>U[i]; E[U[i]].push_back({{S[i],-P[i]},i}); } priority_queue<pair<pair<int,int>,pair<int,int>>> Q; FOR(i,101000) if(E[i].size()) { sort(ALL(E[i])); reverse(ALL(E[i])); FOR(j,E[i].size()) { x = E[i][j].second; Q.push({{S[x],-j},{-P[x],x}}); } } while(K--) { _P("%d\n",Q.top().second.second); Q.pop(); } }
まとめ
tupleが使いやすければこんなにpairを並べないのだけど。