题目描述

有问题，找副连，无聊的时候当然也可以找他啦。小W找到了他的叔叔——东厂厂长——宇宙超级无敌老WS yy。他们叔侄两个商量之后决定用弹弓打破社区里的一些窗户，但是弹弓每秒只能彻底打破一扇窗户。而且如果某户窗户的主人回来了的话，他们就不能进行破坏了（不然会死得很惨的）。因为有的人装的玻璃好，有的人装的玻璃差，有的人装的玻璃高，有的人装的玻璃矮，所以你不能要求他们叔侄两个打破不同的窗户获得的快乐值必须相同。现在他们想知道在能活着的情况下能够获得的最大快乐值。

思路

将时间从大到小排序，那么显然在一个主人先回来的窗户前面的窗可以在这之前的任何时间里打破，每次判断当前点的价值是否为负数，如果是非负数的话，那么我们就讲这个点压入堆中，然后在它距离下一个时间点的时间里，我们可以在堆中取啊a[i].t-1-a[i+1].t个点，就可以了

#include 
#include 
#include 
using namespace std;
#define maxn 200005
struct arr
{
    long long t, w;
}a[maxn];
int cmp(arr a, arr b)
{
    return a.t > b.t;
}
priority_queue,less > q;
int main()
{
    long long n;
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i].t, &a[i].w);
    sort(a + 1, a + n + 1, cmp);
    long long ans = 0;

    for (int i = 1; i <= n; i++)
    {
        if (a[i].w >= 0)
            q.push(a[i].w);
        else continue;
        for (int j = a[i + 1].t; j <= a[i].t - 1; j++)
        {
            ans += q.top();
            q.pop();
            if (q.empty()) break;
        }
    }
    printf("%lld\n", ans);
}

]]>