这道题目和上一道题目类似,但是第
个工作是需要在
或之前做,需要
的时间来做
同样的,需要的是按照截至时间从小到大排序,那么是按照
从小到大排序
不多详解
总代码:
#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;
}



京公网安备 11010502036488号