建筑抢修

https://ac.nowcoder.com/acm/problem/20154
题意：已知每个建筑的报废时间和维修时间，只有一个人去维修，问最多能维修多少建筑？

分析：典型贪心题，我们要在规定时间内维修尽可能多的建筑，大体上先贪心一下，先维修截止时间迫在眉睫的建筑，那么怎么判断当前是否可以进行维修呢（别瞎忙了一阵子发现时间不够），所以我们应当先计算之间花费的时间+维修该建筑所需要的时间是否小于等于结束时间进行判断当前建筑是否能维修。可这样贪心下去，万一有个建筑迫在眉睫但却要占用你全部时间去维修，这样去做不是得不偿失吗？
所以当有一个建筑判断为时间不够维修时，不要把它轻易放弃，前面的可能有些建筑可以放弃掉替换成维修这个，那怎么判断呢？我们可以和之前最长维修时间对比一下，如果当前这个明明截止时间比他靠后却没有他耗时，那为什么不能把前面那个替代了呢？维修总数不变但却省时间，为后面的兄弟营造一丝机会。

主要实现方法：贪心+sort+优先队列

#include<stdio.h>
#include<algorithm>
#include<queue>
using namespace std;
int n,i,j,k,cnt;
struct T{
    int last;
    int end;
}t[200000];
int cmp(T a,T b){
    if(a.end==b.end){
        return a.last<b.last;
    }
    return a.end<b.end;
}
struct f
{
    bool  operator ()(T a,T b) //优先队列降序排列，队头元素为耗时最大的
    {
        return a.last<b.last;
    }
};
int main()
{   
    priority_queue<T,vector<T>,f> q;//优先队列
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d%d",&t[i].last,&t[i].end);
    }
    sort(t,t+n,cmp);//按结束时间先后进行排序
    int time=0;
    for(i=0;i<n;i++){
        if(time+t[i].last<=t[i].end){//能放的就放进去先
            q.push(t[i]);
            cnt++;
            time+=t[i].last;
        }else{
            int maxq=q.top().last;//最长耗时
            if(t[i].last<=maxq){//替换
                q.pop();
                q.push(t[i]);
                time=time-maxq+t[i].last;
            }
        }   
    }
    printf("%d",cnt);
}