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

思路：（可撤销贪心？）先按完成期限对建筑进行升序排序，优先选取完成期限较早的建筑，再用一个堆来维护每个建筑所需的完成时间，如果遍历到所需完成时间比堆顶小（因为此时完成期限为当前建筑中最大的值，此时pop掉堆顶的建筑可能可以让size更大（也就是最终答案））且新的所需时间加和不超过当前建筑完成期限的，则pop原堆顶并push新建筑的所需完成时间即可。

#include <bits/stdc++.h>
using namespace std;

const int Nmax = 2e5;
int n;
long long T_sum;
struct s{
    int d,T;
}a[Nmax];
priority_queue<int,vector<int>,less<int>> heap;
bool comp(s x,s y){    //期限按升序排序
    return x.d < y.d;
}

int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n;
    for(int i = 1;i <= n;i++)
        cin>>a[i].T>>a[i].d;
    sort(a+1,a+1+n,comp);
    for(int i = 1;i <= n;i++){
        if((T_sum+a[i].T) <= a[i].d){
            heap.push(a[i].T);
            T_sum += a[i].T;
        }
        else{
            if(heap.top() >= a[i].T && (T_sum-heap.top()+a[i].T) <= a[i].d){
                T_sum -= heap.top();
                T_sum += a[i].T;
                heap.pop();
                heap.push(a[i].T);
            }
        }
    }
    cout<<heap.size();
    return 0;
}