【题解】 CF1251E2 Voting (Hard Version) 带悔贪心

Legend

Link ( extrm{to Codeforces})。

现在有 (n (1 le n le 2 cdot 10^5)) 个人参与投票，你想让他们都投给你，他们每个人有两个参数 (m_i,p_i)。

第 (i) 个人为你投票有如下两种情况：

• 你主动支付 ta (p_i (1 le p_i le 10^9)) 元；
• 存在 (m_i (0 le m_i < n)) 个其他的人已经投了你。

请最小化所有人都投票给你的花费。

Editorial

考虑花费从小到大贪心，记录当前有多少个人 (vote) 已经为你投票（包括给钱的和跟风的），维护一个集合 (S) 存储：

你主动支付给了 ta 钱，但当初如果你不给 ta 钱，而是给另一个人钱，那么 ta 现在会跟风。

看看维护这个集合有什么用吧：设我现在贪心到的这个人为 (y)，我们找到 (S) 中花费最大的那位朋友 (x)。

如果在当初选 (x) 的时候我选了 (y)，那么现在 (x) 就会跟风，于是就省下了贿赂 (x) 的钱，所以不如直接不选 (x)。

于是我们不断的贪心并且反悔，用 ( m{multiset}) 维护可反悔集合即可。

复杂度 (O(n log n))。

Code

回首一年前的自己，对于此题毫无思路，现在一眼切掉了。虽然我并不强，但人啊，总要进步的，不是吗？

#include <bits/stdc++.h>

using namespace std;

const int MX = 2e5 + 23;

#define LL long long

int read(){
	char k = getchar(); int x = 0;
	while(k < '0' || k > '9') k = getchar();
	while(k >= '0' && k <= '9') x = x * 10 + k - '0' ,k = getchar();
	return x;
}

struct People{
	int p ,m ,id;
	bool operator <(const People &B)const{
		return p == B.p ? m < B.m : p < B.p;
	}
}Pp[MX] ,Pm[MX];

int doit[MX];

bool cmpp(People A ,People B){return A < B;}
bool cmpm(People A ,People B){return A.m < B.m;}

void solve(){
	int n = read();
	
	int vote = 0 ,ok = 1 ,r = 1;
	LL cost = 0;
	for(int i = 1 ,p ,m ; i <= n ; ++i){
		m = read() ,p = read();
		Pp[i] = Pm[i] = (People){p ,m ,i};
		doit[i] = 0;
	}

	sort(Pp + 1 ,Pp + 1 + n ,cmpp);
	sort(Pm + 1 ,Pm + 1 + n ,cmpm);
	
	while(ok <= n && Pm[ok].m <= vote){
		if(!doit[Pm[ok].id]){
			doit[Pm[ok].id] = 1;
			++vote;
		}
		++ok;
	}
	
	multiset<People> change;

	while(vote != n){
		while(doit[Pp[r].id]) ++r;
		cost += Pp[r].p;
		++vote;
		doit[Pp[r].id] = 2;
		
		if(!change.empty()){
			cost -= change.rbegin()->p;
			auto kksk = change.end();
			--kksk;
			change.erase(kksk);
		}
		while(ok <= n && Pm[ok].m <= vote){
			if(!doit[Pm[ok].id]){
				doit[Pm[ok].id] = 1;
				++vote;
			}
			if(doit[Pm[ok].id] == 2){
				change.insert(Pm[ok]);
			}
			++ok;
		}
	}
	cout << cost << endl;
}

int main(){
	int t; cin >> t;
	while(t--) solve();
	return 0;
}