随手写了个贪心,结果30分,求hack。
代码如下:
#include<bits/stdc++.h>
using namespace std;
int n,t1[150010],t2[150010],d,ans;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d%d",&t1[i],&t2[i]);
for(int i=1;i<=n;i++){
if(t2[i]>=t1[i]) q.push(make_pair(t1[i],i));
}
while(!q.empty()){
ans++;
d+=q.top().first;
q.pop();
while(!q.empty()&&t2[q.top().second]<q.top().first+d) q.pop();
}
printf("%d",ans);
return 0;
}