牛客—— [JSOI2007]建筑抢修 （贪心+优先队列）

题意：

有n个建筑需要修理，修理需要时间，如果在限制时间里没有修理完成，就报废了。问最多能够修理多少个建筑。

思路：

贪心。先按时间限制从小到大排序，对于某个建筑，不能修理的话就跟之前修理并且修理花费时间最长比较，如果前者花费时间小，就将后者移除。

维护修理花费时间可以用堆维护。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+7;

struct node{
    ll t1,t2;
    bool operator < (const node &a)const{
        return t2<a.t2;
    }
}a[maxn];

int main(){
    int n;cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i].t1>>a[i].t2;
    sort(a+1,a+1+n);
    int res=0,sum=0;
    priority_queue<int>q;
    for(int i=1;i<=n;i++){
        if(sum+a[i].t1<=a[i].t2){
            res++;
            sum+=a[i].t1;
            q.push(a[i].t1);
        }
        else{
            if(q.top()>a[i].t1){///不判断队列是否为空也可以AC
                    sum=sum-q.top()+a[i].t1;
                    q.pop();
                    q.push(a[i].t1);
                }
            }
    }
    cout<<res<<endl;
    return 0;
}