欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【贪心】JZOJ_3928 射击

程序员文章站 2024-03-13 23:00:16
...

题意

NN个窗户,给出它们的主人回来时间和射击掉它们的快乐值,一个窗户只能在主人回来之前射掉,求出最多能获得的快乐值。

思路

先按时间排序。
维护一个小根堆,每次加入一个窗户就让统计的时间+1,如果当前窗户的主人回来的时间刚好就等于统计的时间,我们与堆顶比较一下,看看是选当前这个窗户优还是堆顶优,最后把堆里剩下的窗户的快乐值统计。

代码

#include<queue>
#include<cstdio>
#include<algorithm>
using namespace std;

priority_queue<long long> q;

struct node{
	long long r, w;
}a[200001];
long long N, t, ans;

int cmp(node x, node y) {
	return x.r < y.r;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%lld %lld", &a[i].r, &a[i].w);
	sort(a + 1, a + N + 1, cmp);
	for (int i = 1; i <= N; i++) {
		if (a[i].w < 0) continue;//注意负数的情况
		if (a[i].r == t && q.size()) {
			if (a[i].w > -q.top()) {
				q.pop();
				q.push(-a[i].w);
			}
		}
		else if (a[i].r > t) {
			q.push(-a[i].w);
			t++;
		}
	}
	while (q.size()) ans += -q.top(), q.pop();
	printf("%lld", ans);
}
相关标签: 贪心