【贪心】JZOJ_3928 射击
程序员文章站
2024-03-13 23:00:16
...
题意
有个窗户,给出它们的主人回来时间和射击掉它们的快乐值,一个窗户只能在主人回来之前射掉,求出最多能获得的快乐值。
思路
先按时间排序。
维护一个小根堆,每次加入一个窗户就让统计的时间+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);
}