[JSOI2007]建筑抢修

题意:给一个维修时间和一个报废的截至时间,然后有很多个,现在问最多抢救多少个
这个题和每日一题第一次的那个题有点像:https://ac.nowcoder.com/discuss/390428
然后回来说这个题.
贪心:先修最先报废的那几个,再修后面的,然后可以用优先队列来实现
然后对于修了x个建筑可能需要t秒,但是对于第y个建筑而言如果把修的x个建筑中的一个不修而修第y个,所需要的时间会小于t,此时有一个状态,即把第y个当x+1来修,还没修完第y个就报废了
所以这用到优先队列
每次返回x个里面消耗时间最多的,与第y个比较,看看那一个所需要的时间比较少

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct node{
    ll x;
    ll y;
} n[150005];
bool cmp(node a,node b){
    return a.y<b.y;
}
priority_queue<ll> q;
int ans,t;
int main(){
    int m;
    cin>>m;
    for(int i=0;i<m;i++){
        scanf("%lld %lld",&n[i].x,&n[i].y);
    }
    sort(n,n+m,cmp);
    for(int i=0;i<m;i++){
        if(t+n[i].x<=n[i].y){
            t=t+n[i].x;
            q.push(n[i].x);
        }
        else{
            if(n[i].x<q.top()){
                t=t-q.top()+n[i].x;
                q.pop();
                q.push(n[i].x);
            }
        }
    }
    cout<<q.size()<<endl;
    return 0;
}