Bzoj1029--Jsoi2007建筑抢修

贪心

先按终止时间排一次序，能抢修的就抢修

如果超过了时间限制，就和之前加入的时间最长的点比较，如果这个建筑的t1<max(t1)，因为我们是按t2升序排列，所以不修之前建筑的话这个建筑肯定能修，并且不会使解变差，如果这个建筑t1>max(t1)那么加入这个建筑就会使解变差

代码：

#include<bits/stdc++.h>
#define MAXN 150005
#define MAXM 30005
#define INF 1000000000000
#define eps 1e-9
#define LL long long
using namespace std;

inline int _max(int a,int b) {return a>b?a:b;}

struct Task{
    int cs,ed;
    bool operator < (const Task &b) const {
        return ed<b.ed;
    }
}t[MAXN];
int n,ans;LL nc;
priority_queue<int> q;

int main() {
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d%d",&t[i].cs,&t[i].ed);
    sort(t+1,t+1+n);q.push(0);
    for(int k,i=1;i<=n;i++) {
        if(t[i].cs+nc<=t[i].ed) q.push(t[i].cs),nc+=t[i].cs,ans++;
        else {
            k=q.top();
            if(t[i].cs>=k) continue;
            nc=nc-k+t[i].cs;q.pop();q.push(t[i].cs);
        }
    }
    cout<<ans<<endl;
    return 0;
}