P2949 [USACO09OPEN]工作调度Work Scheduling

题目描述

约翰有太多的工作要做。为了让农场高效运转，他必须靠他的工作赚钱，每项工作花一个单位时间。他的工作日从0时刻开始，有10^8个单位时间。在任一时刻，他都可以选择编号1~N的N(1 <= N <= 10^6)项工作中的任意一项工作来完成。因为他在每个单位时间里只能做一个工作，而每项工作又有一个截止日期，所以他很难有时间完成所有N个工作，虽然还是有可能。对于第i个工作，有一个截止时间D_i(1 <= D_i <= 10^9)，如果他可以完成这个工作，那么他可以获利P_i( 1<=P_i<=10^9 ). 在给定的工作利润和截止时间下，约翰能够获得的利润最大为多少.

输入输出格式

输入格式：

* Line 1: A single integer: N

* Lines 2..N+1: Line i+1 contains two space-separated integers: D_i and P_i

输出格式：

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

输入输出样例

输入样例#1：

输出样例#1：

说明

Complete job 3 (1,7) at time 1 and complete job 1 (2,10) at time 2 to maximize the earnings (7 + 10 -> 17).

Solution

这道题我一开始是往DP方向想的,结果尴尬地发现自己不造怎么定义状态... 于是就想贪心水分.

结果想了一个自己觉得是正解的贪心做法.然后发现只得了33分...

又调了良久,还是33分.

然后一看题解,发现题解只不过是把我的思路倒过来. 然后就对了.很显然我还是太菜了.

这道题的贪心的策略就是：

先把所有的价值都加进去.然后同步统计一个now统计时间.

如果当前时间已经超过了实现,那么我们就减掉价值最小的.

然后这个价值最小的用一个堆就可以维护.

代码

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int maxn=;

struct sj{

    ll d;

    ll p;

}a[maxn];

priority_queue <int> q;

ll read()

{

    char ch=getchar(); ll f=,w=;

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch<=''&&ch>=''){w=w*+ch-'';ch=getchar();}

    return f*w;

}

bool cmp(sj s,sj j){if(s.d!=j.d)return s.d<j.d;else return s.p<j.p;}

ll ans,maxt,n;

ll num,maxs[maxn];

int main()

{

    n=read();

    for(int i=;i<=n;i++) a[i].d=read(),a[i].p=read();

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

    ll old=;

    int now=;

        for(int i=;i<=n;i++)

    {

        ans+=a[i].p;

        now++;

        q.push(-a[i].p);

        //大根堆转小根堆

        if(now>a[i].d)

        {

            ans+=q.top(),q.pop();now--;

        }

    }

    cout<<ans<<endl;

}

然后这是我的错误贪心：

  for(int i=n;i>=;i--)

    {

        if(a[i].d!=old)

        {

            ll tt=old-a[i].d;

            old=a[i].d;

            while(tt!=)

            {

                int t=q.top();

                q.pop();

                ans+=a[t].p;

                tt--;

            }

        }

        q.push(i);

    }

巴特西