题解 | #[JSOI2007]建筑抢修#

可反悔的贪心。从小到大对倒塌时长排序，先修快倒塌的（从小到大枚举修理时长）。如果时间不够修当前的楼，就先判断这个楼是否有必要修（修它的用时<修之前楼用时的最大值，就有必要修）。如果没必要就不修，如果有必要就把前面修的时间最长的楼去掉，不去修它。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll> q;//大根堆
struct build{
    ll t1;
    ll t2;
}a[150010]; 
ll n;
int comp(struct build x,struct build y){//按照倒塌时长从小到大排序 
    return x.t2<y.t2;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i].t1 >> a[i].t2;
    sort(a,a+n,comp);
    ll pt=0;//已经过去的时间pass time 
    ll saved=0;//已经修好的楼 
    ll maxsaved=0;//最多能修好的楼 
    for(int i=0;i<n;i++){
        if(pt+a[i].t1<a[i].t2){//能修好 
            q.push(a[i].t1);
            pt+=a[i].t1;
            saved++;
            maxsaved=max(maxsaved,saved);
        }
        else{//时间不够，修不好 
            if(a[i].t1<q.top()){//当前的楼用时不是最多，有必要修当前的楼
                while(pt+a[i].t1>a[i].t2){//把前面时间长的扔了，修当前这个
                    ll x = q.top();
                    q.pop();
                    pt-=x;
                    saved--;
                }
                q.push(a[i].t1);
                pt+=a[i].t1;
                saved++;
                maxsaved=max(maxsaved,saved);
            }
        }
    }
    cout << maxsaved << "\n";
    return 0;
}

---------------------一个优化--------------------------
先假设当前这个楼能修，直接放进堆里。如果发现这个楼需要修(修这个楼用时<大根堆的堆顶)，就从这个堆中把修理用时长的楼删去

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
priority_queue<ll> q;//大根堆
struct build{
    ll t1;
    ll t2;
}a[150010]; 
ll n;
int comp(struct build x,struct build y){//按照倒塌时长从小到大排序 
    return x.t2<y.t2;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i].t1 >> a[i].t2;
    sort(a,a+n,comp);
    ll pt=0;//已经过去的时间pass time 
    ll saved=0;//已经修好的楼 
    ll maxsaved=0;//最多能修好的楼 
    for(int i=0;i<n;i++){
        //先假设能修
        q.push(a[i].t1);
        pt+=a[i].t1;
        saved++;
        while(a[i].t1<=q.top() && pt>a[i].t2){//当前的楼要修，且时间不够，就删去其他用时长的楼
            ll x = q.top();
            q.pop();
            pt-=x;
            saved--;
        }
        maxsaved=max(maxsaved,saved);
    }
    cout << maxsaved << "\n";
    return 0;
}