题解 | 洛谷P11457 [USACO24DEC] Job Completion G #

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

#define endl '\n'
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define HelloWorld IOS;


bool cmp(pair<int, int> a, pair<int, int> b){
    return a.first + a.second < b.first + b.second;
}

void solve(){
    int n; cin >> n;
    vector<pair<int, int> > a(n + 1);
    for(int i = 1; i <= n; i ++) cin >> a[i].first >> a[i].second;
    sort(a.begin() + 1, a.begin() + 1 + n, cmp);    

    priority_queue<int> q;
    int time = 0;
    for(int i = 1; i <= n; i ++){
        if(time <= a[i].first){
            time += a[i].second;
            q.push(a[i].second);
        }
        else if(q.size() && q.top() > time - a[i].first && q.top() > a[i].second){
            time += a[i].second - q.top();
            q.pop();
            q.push(a[i].second);
        }
    }
    cout << q.size() << endl;
}
signed main(){
    HelloWorld;
    
    int tt; cin >> tt;
    while(tt --) solve();
    return 0;
}