AC日记——最高奖励 51nod 1163

最高的奖励

思路：

　　排序；

　　时间为第一关键字，按总小到大排；

　　价值为第二关键字，按从大到小排；

　　然后，不难看出，如果两个时间不同；

　　那么，两个时间之间最少能做一件事；

　　因为他们的时间下限最少相差1；

　　然后我们记录每个时间要做的事；

　　如果同一时间要做很多事，则选择其中最大的一个；

　　看似正确的题解，其实很不对。。。

　　我们需要用一个堆来记录已经做了的事的最小值；

　　如果遇到一个因为时间限制不能做的事，则判断当前的事的价值是否大于堆顶；

　　如果大于，则ans+=当前事的价值-堆顶，然后堆顶出队，当前事的价值入队；

　　如果还是不懂看代码吧。。。

来，上代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define maxn 50005

struct NodeType {
    int ti,ci;
};
struct NodeType ai[maxn];

int n;

long long ans;

priority_queue<int>que;

inline void in(int &now)
{
    char Cget=getchar();now=0;
    while(Cget>'9'||Cget<'0') Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}

inline bool cmp(NodeType iposa,NodeType iposb)
{
    if(iposa.ti==iposb.ti) return iposa.ci>iposb.ci;
    else return iposa.ti<iposb.ti;
}

int main()
{
    in(n);int cnt=0;
    for(int i=1;i<=n;i++) in(ai[i].ti),in(ai[i].ci);
    sort(ai+1,ai+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        if(cnt<ai[i].ti) cnt++,ans+=ai[i].ci,que.push(-ai[i].ci);
        else
        {
            int op=-que.top();
            if(ai[i].ci>op)
            {
                ans-=op,que.pop(),ans+=ai[i].ci;
                que.push(-ai[i].ci);
            }
        }
    }
    cout<<ans;
    return 0;
}