Codeforce 1271 D. Portals（思维 + 贪心）

程序员文章站 2024-03-19 11:47:04

...

题目大意：有 n 个待攻破的点，每个点有三个权值a,b,c，代表攻破这个点需要至少a个士兵，攻破完后你能招纳b个士兵，这个点的重要度为c，除此之外还存在一些有向边u,v 满足 u > v。攻破一个点不会损耗士兵，但你的士兵数量必须不小于这个点的a值才可以攻破。

每攻破一个点你都可以派人驻守（可以派一个或多个），当一个点有人驻守时你就可以获得这个点的重要度，如果你派出一个人去驻守，那么你当前的军队的士兵数就会减少1。当你在u点时，你可以派人驻守 u 和 v（前提是u,v之间有一条有向边）。

初始时你有k个士兵，你必须按编号 1 - n 的顺序来攻破所有的点，问当你攻破所有点后你可以获得的最大重要度是多少，如果不能全部攻破那么输出 -1.

考虑贪心维护攻破每一个城市你能驻守的获益最大的点集，设当前你已有 $x$ 个士兵，你正准备攻破第 $y$ 个点，显然你前面最多能驻守 $x - y_a$ 个点。用 set 维护前面驻守的点，若 $x - y_a < set.size()$ ，那么保留set中权值较大的 $x - y_a$ 个点。

当你攻破第 y 个点后，你现在拥有 $x + y_b$ 个士兵，除了前面驻守的 $x-y_a$ 个点外，你还能考虑驻守 $y$ 和所有 $y$ 能到达的点。用另外一个set将这些点统一起来，然后取权值较大的 $x + y_b$ 个，维护到你当前驻守的set集中。

问题：
当你只能保留 $x-y_a$ 个点时，贪心的策略是保留权值最大的 $x-y_a$ 个点，逐出剩下的点，一个问题就是当你攻占完 y 后，你又可以考虑驻守 y 以及 y所有能到达的点，这些点可能会和前面维护的驻守点有重复。这意味着你在攻占某一个点时不得不逐出一些点，但你在后面某个时刻还能考虑到这些点，因此这个贪心策略不完全正确。

当需要逐出一些点时，有限逐出后面还有机会遇到的点，因为即使把他们逐出了，后面在攻破某些点时还有机会考虑是否需要派人驻守这些点。set中应按这个点剩余的可遇到的次数作第一关键字排序，重要度作第二关键字来排序。

当你攻破最后一个点时，所有点的剩余可遇到次数都为0，你将按权值筛选较大的 $x$ 个来驻守，在此之前你尽可能保留那些即将没有机会遇到的点以便后面可以作出更全面的决策，这显然是合理的。

多注意一些实现细节即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 4e5 + 10;
#define  pii pair<int,int>
int n,m,k;
struct node{
	int a,b,c;
}p[maxn];
int vis[5100],use[5100];
struct ss{
	int c,v;
	ss(int ci = 0,int vi = 0) {
		c = ci;
		v = vi;
	}
	bool operator < (const ss &rhs) const {
		if(vis[v] == vis[rhs.v]) {
			if(c == rhs.c) return v < rhs.v;
			return c < rhs.c;
		}
		return vis[v] > vis[rhs.v];
	}
};
multiset<ss> st,tp,g[maxn];
int main() {
	scanf("%d%d%d",&n,&m,&k);
	for(int i = 1; i <= n; i++) {
		scanf("%d%d%d",&p[i].a,&p[i].b,&p[i].c);
	}
	for(int i = 1; i <= m; i++) {
		int u,v;scanf("%d%d",&u,&v);
		if(u < v) swap(u,v);
		g[u].insert(ss(p[v].c,v));
		vis[v]++;
	}
	int cur = k; 
	bool f = true;
	for(int i = 1; i <= n; i++) {
		if(p[i].a > cur) {
			f = false;
			break;
		} else {
			int x = cur - p[i].a;			//在这个点之前可以用来占领地方的人 
			cur += p[i].b;					//打完后当前的人 		
			while(st.size() > x) {			//前面留下的可以防守的 
				st.erase(st.begin());
			}
			int tmp = cur;
			tp.clear();
			memset(use,0,sizeof use);
			for(auto it : st) {
				use[it.v] = 1;
				tp.insert(it);
			}
			for(auto it : g[i]) {
				if(use[it.v]) 
					tp.erase(it);
				vis[it.v]--;
				tp.insert(it);
				use[it.v] = 1;
			}
			tp.insert(ss(p[i].c,i));
			st.clear();
			for(auto it = tp.rbegin(); it != tp.rend() && tmp > 0; it++) {
				st.insert(*it);
				tmp--;
			}
		}
	}
	if(!f) puts("-1");
	else {
		int sum = 0;
		for(auto it : st)
			sum += it.c;
		printf("%d\n",sum);
	}
	return 0;
}