题目大意:
给定n个任务,每个任务完成所需时间和截止完成时间,求最多能完成多少个任务.
分析:考虑贪心策略。
我们每次选择任务完成一定是要最后完成任务的时间尽可能的小,并且当前的时间加上完成当前选择任务的时间一定要小于任务的截止时间才有效。这个我们可以将所有任务按照截止时间排序。那么对于当前时间加上任务完成所需时间小于截止时间的任务可以直接进行完成。
那么如果当前时间加上任务完成所需时间大于截止时间的时候,我们是否可以从已经完成任务中 选择一个最大完成任务所需时间的任务 踢出,然后将新任务加入进来.那么执行这种操作一定是要已完成的最大完成任务所需时间要大于将新任务完成的时间,这样可以使得当前完成所有选择任务的终止时间尽可能小,并且踢出和加入完成任务个数答案不变。选择一个最大完成任务所需时间的任务我们可以用一个堆维护.
#include<bits/stdc++.h> using namespace std; const int mod=1e9+7; typedef long long ll; const int maxn=2e5+10; pair<int,int> p[maxn]; int main() { int n; cin>>n; for( int i=1;i<=n;i++ ) cin>>p[i].second>>p[i].first; sort(p+1,p+1+n); priority_queue<int>q; ll now=0,res=0; for( int i=1;i<=n;i++ ) { if( now+p[i].second<=p[i].first ) { now+=p[i].second; res++; q.push(p[i].second); } else { if( q.empty() ) continue; if( q.top()>p[i].second ) { now-=q.top();q.pop(); now+=p[i].second;q.push(p[i].second); } } } cout<<res<<endl; }