51nod 1163 最高的奖励（贪心+堆）

题意：有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。

思路：建立一个以任务的奖金为权值的小根堆，初始堆空，用len记录堆的规模（堆中元素个数）。 对任务按截止时间 t[i] 从小到大排序，按序枚举每个任务，此时len有两种情况： 

1.len < t[i], 选择该任务，将任务的奖金插入堆中。

2.len > t[i]，若该任务的奖金比堆中最小奖金值更大，则弹出堆顶元素，将该任务的奖金入堆。

代码：

#include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn = 5e4+5;
struct node
{
    int t, w;
    bool operator < (const node &a) const
    {
        return t < a.t;
    }
}a[maxn];

int main(void)
{
    int n;
    while(cin >> n)
    {
        for(int i = 1; i <= n; i++)
            scanf("%d%d", &a[i].t, &a[i].w);
        sort(a+1, a+1+n);
        priority_queue<int, vector<int>, greater<int> > pq;
        ll ans = 0;
        for(int i = 1; i <= n; i++)
        {
            if(pq.size() < a[i].t)
            {
                ans += a[i].w;
                pq.push(a[i].w);
            }
            else
            {
                ans += a[i].w;
                pq.push(a[i].w);
                ans -= pq.top();
                pq.pop();
            }
        }
        printf("%lldn", ans);
    }
    return 0;
}

最后

以上就是怡然帆布鞋为你收集整理的51nod 1163 最高的奖励（贪心+堆）的全部内容，希望文章能够帮你解决51nod 1163 最高的奖励（贪心+堆）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。