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=;

    while(Cget>''||Cget<'') Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        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=;

    for(int i=;i<=n;i++) in(ai[i].ti),in(ai[i].ci);

    sort(ai+,ai+n+,cmp);

    for(int i=;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 ;

}

巴特西

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

最新文章

热门文章