训练计划

思路与复杂度

按截止时间排序，依次把任务加入已选集合并累计耗时。若超过当前截止时间，删去集合中耗时最长的任务。这样在保留最多任务数的同时使累计耗时最小，给后续任务留下最大余量。时间 O(n log n)，空间 O(n)，累计耗时用64位整数。

正确性与边界

超时集合若必须删一项，删最长耗时留下的总耗时最少，不影响最优数量。

参考代码

#include<bits/stdc++.h>
using namespace std;int main(){ios::sync_with_stdio(0);cin.tie(0);int n;cin>>n;vector<pair<long long,long long>>a(n);for(auto&x:a)cin>>x.second>>x.first;sort(a.begin(),a.end());priority_queue<long long>q;long long s=0;for(auto[d,t]:a){s+=t;q.push(t);if(s>d)s-=q.top(),q.pop();}cout<<q.size()<<"\n";}