[原创]51nod 1163 最高的奖励 [贪心]【杂类】

2017-03-02 12:40:48 Tabris_ 阅读数：234

博客爬取于2020-06-14 22:41:31
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/59488912

题目连接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1163
-----------------------------------------------------------------------------------------------.
1163 最高的奖励
基准时间限制：1 秒空间限制：131072 KB 分值: 20 难度：3级算法题收藏关注
有N个任务，每个任务有一个最晚结束时间以及一个对应的奖励。在结束时间之前完成该任务，就可以获得对应的奖励。完成每一个任务所需的时间都是1个单位时间。有时候完成所有任务是不可能的，因为时间上可能会有冲突，这需要你来取舍。求能够获得的最高奖励。
Input
第1行：一个数N，表示任务的数量(2 <= N <= 50000)
第2 - N + 1行，每行2个数，中间用空格分隔，表示任务的最晚结束时间E[i]以及对应的奖励W[i]。(1 <= E[i] <= 10^9，1 <= W[i] <= 10^9)
Output
输出能够获得的最高奖励。
Input示例
7
4 20
2 60
4 70
3 40
1 30
4 50
6 10
Output示例
230
------------------------------------------------------------------------------------------------.
解题思路:

本题看别人的思路都是贪心+优先队列

按照题意，可以从最晚结束时间和完成任务奖励分别展开求解。
从最晚结束时间考虑贪心策略的话，那么应该将最晚结束时间升序排序。
具体(PS):
用贪心思想，从0开始，每完成一件任务，消耗时间为1，按最晚时间递增，第n个任务如果最晚时间大于已消耗掉时间量，则可算入总和，若不大于已耗时间量，
则可以替换掉总和里最小奖励的一个任务(如果当前任务的奖励更多的话)。
这个过程可以用堆维护。nlog(n);

然而我是贪心+双数组

定义h[]数组,表示 $h_i$ 时刻内做没有做任务
定义m[]数组,表示一个"指针"，指向距离 $m_i$ 时间点最近的没有做任务的时间点 $(m_i\leq i)$ 。~~其实这一步有点像并查集~~

排序的时候以w递减，e没什么所谓。
然后一次遍历，判断这个任务能不能做，能做就计算上。

排序是 $O(n\log(n))$ 的,在统计的时候确实 $O(n)$ 的

贪心+优先队列
------------------------------------------------------------------------------------------------.

# include"stdio.h"
# include"algorithm"
# include"queue"
using namespace std;
const int maxn=5e4+5;
struct task{
    int times;
    int cost;
}t[maxn];
bool cmp(const task a,const task b)
{
    if(a.times<b.times) return true;
    return false;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&t[i].times,&t[i].cost);
    }
    sort(t,t+n,cmp);
    priority_queue<int ,vector<int >,greater<int> >pq;
    long long  ans=0;
    for(int i=0;i<n;i++)
    {
        int k=t[i].cost;
        if(t[i].times>pq.size()) //pq.size这里理解代表时间点
        {
            ans+=k;
            pq.push(k);
        }
        else//时间点有冲突，把cost最小删除
        {
            ans+=k;
            pq.push(k);
            int minn=pq.top();
            ans-=minn;
            pq.pop();//删除
        }
    }
    printf("%lld\n",ans);
    return 0;
}

贪心+加上双数组
------------------------------------------------------------------------------------------------.

struct node {
    int e,w;
}a[N];

bool cmp(node A,node B){
    //if(A.w==B.w)return A.e<B.e;
    return A.w>B.w;
}

int m[N];  //指针，指向距离当前时间点最近的没有做任务的时间点。
bool h[N]; //判断当前时间点有没有做任务。

int main(){
    int n;
    scanf("%d",&n);
    h[0]=1;
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].e,&a[i].w);
        h[i]=0;
        m[i]=i;
    }
    sort(a+1,a+n+1,cmp);
    LL ans = 0;
    //lalal;
    for(int i=1;i<=n;i++){
        //printf("%d %d\n",a[i].e,a[i].w);

        int now = m[a[i].e];
        while(h[now]&&now>0){
            now = m[now-1]; //切记要减1
            //printf("%d %d   %d %d\n",now,m[now],h[now],h[m[now]]);
        }
        if(now<0)now=0;
        m[a[i].e]=now;

        if(!h[m[a[i].e]]){
            ans+=a[i].w;
            h[m[a[i].e]]=1;
            m[a[i].e]--;
            //printf("---\n");
        }

        //for(int i=1;i<=n;i++)  printf("%d%c",h[i],(i==n)?'\n':' ');
        //for(int i=1;i<=n;i++)  printf("%d%c",m[i],(i==n)?'\n':' ');
    }

    printf("%lld\n",ans);
    return 0;
}