ferinの競プロ帳

競プロについてのメモ

Educational Codeforces Round 75 E2. Voting (Hard Version)

問題ページ
m_i=n-1 の人を無料で投票させるのには,他の人全員から投票されていなければならない.したがって,m_i=n-1 の人から1人(=最も買収するのにお金がかかる人)以外は必ず買収する必要がある.
m_i=n-2 の人を無料で投票させるには,m_i - (m_in-2未満の人数) - (m_i=n-1で買収した人数) 人を m_i \geq n-2 の人から買収する必要がある.
同様に m_i=x について降順に考える.

  • x - (m_ix未満の人数) - (m_i=xまでで買収した人数) \leq 0 の場合
    追加で買収する必要はない
  • x - (m_ix未満の人数) - (m_i=xまでで買収した人数)  \gt  0 の場合
    m_i \geq x の人のうち p_i が小さい方から x - (m_ix未満の人数) - (m_i=xまでで買収した人数) 人を買収する

multiset等を用いて p_i を昇順に並べておくことでこの操作は十分高速にできる.

#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;  
}