贪心。
显然的,肯定是以结束时间为关键字从小到大排序。为什么?
结束时间早点完成后,然后尽可能有更多时间去修复下一个即可。
那么可能出现当前花费的时间加上当前修复的时间会超过时间要求,
这时候可以选择这个点不修复,跳过,可以选择再前面完成的里面,选取一个不修复,然后多出来的时间用来修复这个。
怎么处理?
如果我当前这个只需要花费5就能修复,而已修复的里面有个需要花费10的才能修复,那么完全可以抛弃已修复的10,然后来修复这个花费5的。
因为这样可以再更短的时间内修复一样的个数,然后多余的时间就可以分配给后面的点。
#include<bits/stdc++.h> using namespace std; pair<int,int> a[1500005]; #define x first #define y second int main(){ int n;cin>>n; for(int i=1;i<=n;i++){ cin>>a[i].y>>a[i].x; } sort(a+1,a+1+n); priority_queue<int> q; int now=0,ans=0; for(int i=1;i<=n;i++){ if(now+a[i].y<=a[i].x){ now+=a[i].y; ans++; q.push(a[i].y); } else if(q.top()>a[i].y){ now-=q.top(),now+=a[i].y; q.pop(); q.push(a[i].y); } } cout<<ans<<endl; return 0; }