bzoj 1029 [ JSOI 2007 ] 建筑抢修 —— 贪心

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=1029

想不出来贪心...

首先把任务按结束时间排序；

因为任务一定是越提前做越好，所以从头开始往后做任务，时间增加，记录 nw；

新加入一个任务，如果能够完成，那么完成即可；

如果不行，从已经完成的任务中找一个替换使时间提前的，这样答案不变但是 nw 更小，为后面提供更大的空间；

注意替换掉的要比当前任务花费的时间长！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

int const maxn=;

int n,nw,ans;

priority_queue<int>q;

struct N{int t,d;}p[maxn];

bool cmp(N x,N y){return x.d<y.d;}

int main()

{

    scanf("%d",&n);

    for(int i=;i<=n;i++)scanf("%d%d",&p[i].t,&p[i].d);

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

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

    {

        if(nw+p[i].t<=p[i].d)

        {

            nw+=p[i].t; ans++;

            q.push(p[i].t);

        }

        else if(q.size()&&q.top()>p[i].t&&nw-q.top()+p[i].t<=p[i].d)//q.top()>p[i].t!

        {

            nw-=q.top(); nw+=p[i].t;

            q.pop(); q.push(p[i].t);

        }

    }

    printf("%d",ans);

    return ;

}