Educational Codeforces Round 75 E2. Voting (Hard Version)
問題ページ
の人を無料で投票させるのには,他の人全員から投票されていなければならない.したがって, の人から1人(最も買収するのにお金がかかる人)以外は必ず買収する必要がある.
の人を無料で投票させるには,が未満の人数で買収した人数 人を の人から買収する必要がある.
同様に について降順に考える.
- が未満の人数までで買収した人数 の場合
追加で買収する必要はない - が未満の人数までで買収した人数 の場合
の人のうち が小さい方から が未満の人数までで買収した人数 人を買収する
multiset等を用いて を昇順に並べておくことでこの操作は十分高速にできる.
#include <bits/stdc++.h> using namespace std; using ll = long long; using PII = pair<ll, ll>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() template<typename T> void chmin(T &a, const T &b) { a = min(a, b); } template<typename T> void chmax(T &a, const T &b) { a = max(a, b); } struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio; #ifdef DEBUG_ #include "../program_contest_library/memo/dump.hpp" #else #define dump(...) #endif const ll INF = 1LL<<60; void solve() { ll n; cin >> n; vector<vector<ll>> v(n); REP(i, n) { ll m, p; cin >> m >> p; v[m].push_back(p); } multiset<ll> st; ll ret = 0, pre = n, cnt = 0; for(ll i=n-1; i>=0; --i) { pre -= v[i].size(); for(auto j: v[i]) st.insert(j); ll need = i - pre; while(cnt < need) { ret += *st.begin(); st.erase(st.begin()); cnt++; } } cout << ret << endl; } int main(void) { ll t; cin >> t; while(t--) solve(); return 0; }