题目描述

Farmer John has so very many jobs to do! In order to run the farm efficiently, he must make money on the jobs he does, each one of which takes just one time unit.
His work day starts at time 0 and has 1,000,000,000 time units (!). He currently can choose from any of jobs conveniently numbered 1..N for work to do. It is possible but extremely unlikely that he has time for all N jobs since he can only work on one job during any time unit and the deadlines tend to fall so that he can not perform all the tasks.
Job i has deadline . If he finishes job i by then, he makes a profit of .
What is the maximum total profit that FJ can earn from a given list of jobs and deadlines? The answer might not fit into a 32-bit integer.

输入描述:

* Line 1: A single integer: N
* Lines 2..N+1: Line i+1 contains two space-separated integers: and

输出描述:

* Line 1: A single number on a line by itself that is the maximum possible profit FJ can earn.

示例1

输入
3 
2 10 
1 5 
1 7 
输出
17
说明
Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

解答

这道题的思路很神奇，是一种可以后悔的贪心。
解题思路：
我们先将每一个任务按照限制时间排序。
对于每一种任务，我们有两种抉择：
for(int i=1;i<=n;++i)
{
    if(a[i].d<=q.size())//即是当前这个任务在限制时间内无法完成。
    {
        //那么就在前面找到价值比当前的任务小的价值最小的任务，将其替换。
    }
    else
    {
        //直接塞入储存任务的数组
        ++time_now;
    }
}
在上面的思路中，我们需要寻找最小的任务价值，就可以利用优先队列（小根堆），那么上面的思路就整理如下： 
for(int i=1;i<=n;++i)
{
    if(a[i].d<=q.size())
    {
        if(a[i].p>q.top().p)
        {
            ans+=a[i].p-q.top().p;
            q.pop();
            q.push(a[i]);
        }
    }
    else
    {
        ans+=a[i].p;
        q.push(a[i]);
    }
}
完整代码： 
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
#define int long long
struct Work
{
    int d,p;
    bool operator > (const Work a) const
    {
        return p<a.p;
    }
    bool operator < (const Work a) const
    {
        return p>a.p;
    }
};
Work a[1000005];
bool cmp(Work a,Work b)
{
    return a.d<b.d;
}
priority_queue <Work> q;
int n,ans=0;
signed main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%lld%lld",&a[i].d,&a[i].p);
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;++i)
    {
        if(a[i].d<=q.size())
        {
            if(a[i].p>q.top().p)
            {
                ans+=a[i].p-q.top().p;
                q.pop();
                q.push(a[i]);
            }
        }
        else
        {
            ans+=a[i].p;
            q.push(a[i]);
        }
    }
    printf("%lld",ans);
    return 0;
}



来源：Point-King