题解 P11457

· · 题解

题意：

有一些必须不间断做的工作，有最晚起始时间和消耗时间长度，问最多可以完成多少工作。

思路：

赛时把工作直接按照起始时间排序，原地趋势。

板题的反悔贪心，把工作按照最晚结束时间排序。

维护一个大根堆，从大到小给所做的所有工作按时间长短排序。然后顺序遍历所有工作，如果当前工作可以做，就加入大根堆。如果当前工作不能做，将它和堆里最大的数进行比较。如果它比堆里最大的工作时间短，而且将堆里最大的工作时间去掉后可以做当前的工作，那就可以直接将堆里最大的值抛掉，新的工作时间压入堆。

最终结果即为堆的大小。

可以证明上述方法正确，在需要更换堆中元素时总时长不减，同时工作数只会单调递增。时间复杂度 O(Tn\log n)。

注意开 long long 以及多测清空堆。

代码如下：

#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N=2e5+5;
int T,n;
struct JOB{long long s,t;}a[N];
bool operator<(JOB x,JOB y){return x.t==y.t?x.s<y.s:x.t<y.t;}
bool cmp(JOB x,JOB y){return x.s+x.t<y.s+y.t;}
priority_queue<JOB,vector<JOB>,less<JOB> >q;
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].s,&a[i].t);
        while(!q.empty())q.pop();
        sort(a+1,a+n+1,cmp);
        long long curt=0;
        for(int i=1;i<=n;i++){
            if(curt<=a[i].s){
                q.push(a[i]);
                curt+=a[i].t;
            }
            else{
                JOB u=q.top();
                if(a[i].t<u.t&&curt-u.t<=a[i].s){
                    q.pop();
                    curt-=u.t;
                    q.push(a[i]);
                    curt+=a[i].t;
                }
            }
        }
        printf("%d\n",q.size());
    }
    return 0;
}

THE END