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

//贪心  2025寒假牛客集训1视频讲解
/*先按结束时间从小到大排序
  然后枚举每个结束时间 从最小的修理时间开始加入队列里
  队头是当前加入的最耗时的修理时间 
  遇到更优的（更短的修理时间）就换
*/

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
using namespace std;
typedef pair<int,int> pii;
const int N=2e5+9;
priority_queue<int>q;
pii a[N];
int ans;
signed main(){
    int n,t,ed;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>t>>ed;
        a[i]={ed,t};
    }
    sort(a+1,a+1+n);
    int cnt=0;
    for(int i=1;i<=n;i++){
        if(cnt+a[i].se<=a[i].fi){
            ans++;cnt+=a[i].se;
            q.push(a[i].se);
        }
        else if(q.top()>a[i].se){
            cnt-=q.top();q.pop();
            cnt+=a[i].se;
            q.push(a[i].se);
        }
    }
    
    cout<<ans;
    
    
    return 0;
}