http://codeforces.com/contest/1019/problem/A
N人の有権者とM種類の政党がある。
i番目の人はもともとP[i]番目の政党に投票しているが、C[i]円支払うことで別の政党に投票してくれる。
1番目の政党が選挙で勝つには最小でいくら必要か。
※選挙で勝つには他の政党よりも多くの票を集める必要がある（同じ票数は駄目）
考察過程
1. 3*10^3なので、2乗くらいなら間に合う感じがある
2. なにか全探索するものを考える→1番目の政党が最終的に集めた票数で全探索が良いのでは？
3. 1番目の政党が集めた票数が分かれば、それ以上の票数を持っている他の政党から票を何票奪えばいいか分かる
4. 奪う場合はコストが小さい人から説得すればよい（priority_queue）
5. 最後にまだ票数が足りてない場合は全体を見て、小さい人から説得する（priority_queue）
解法
http://codeforces.com/contest/1019/submission/41487872
この解法はO(NMlogM)解法であるが、かなりギリギリである。
うまくやればlogが取れるらしい（O(N(N+M))があるとTLで見た気がする）。
solve(win) := 1番目の政党がwin票だけ集めて選挙に勝った場合に必要な最小コスト
これを1～N/2くらいまで回して最小コストが答えになる。
solve関数内では、政党毎に以下の処理を行う
1. priority_queueを使って、コストが小さい順に取り出せるようにしておく
2. 票数がwin以上であれば、win未満になるように、コストが小さい順に説得していく
3. win未満になったら、残りは全体のpriority_queueに入れておく
これで全ての政党はwin未満にすることができた。
場合によっては、これをしただけでは1番目の政党の獲得票数がwin以上になっていない場合があるので、
手順3で作った全体のpriority_queueを使って、1番目の政党の各得票数がwin以上になるように取っていく。
int N, M, P[3010], C[3010]; template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>; //--------------------------------------------------------------------------------------------------- ll solve(int win) { ll res = 0; map<int, min_priority_queue<int>> que; min_priority_queue<int> all; rep(i, 0, N) que[P[i]].push(C[i]); int me = que[1].size(); fore(p, que) { int party = p.first; auto cost = p.second; if (party == 1) continue; while (win <= cost.size()) { res += cost.top(); cost.pop(); me++; } while (!cost.empty()) { all.push(cost.top()); cost.pop(); } } while (me < win) { me++; res += all.top(); all.pop(); } return res; } //--------------------------------------------------------------------------------------------------- void _main() { cin >> N >> M; rep(i, 0, N) cin >> P[i] >> C[i]; ll ans = infl; rep(win, 1, min(N + 1, N / 2 + 5)) chmin(ans, solve(win)); cout << ans << endl; }
