大家好，我是传奇蒟蒻！
刚刚玩了一下kenji's life，在CTSC时被虐了……
还是太弱了啊，游戏里都被虐
先写简单题感受一下神犇们的嘲讽。
这题使用小根堆维护，然后套个贪心就没了。
#include<cstdio>
#include<cstdlib>
#include<queue>
#include<algorithm>
using namespace std;
int n,ans=0,now=0;
struct Node{
int t1,t2,flg;
friend bool operator < (const Node&a ,const Node&b){
return a.t1<b.t1?1:0;
}
}a[150005];
priority_queue <Node> Q;
int cmp(const void *a,const void *b){
if((*(Node *)a).t2==(*(Node *)b).t2)return (*(Node *)a).t1-(*(Node *)b).t1;
return (*(Node *)a).t2-(*(Node *)b).t2;
}
int main(){
freopen("1029.in","r",stdin);
freopen("1029.out","w",stdout);
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%d %d",&a[i].t1,&a[i].t2);
a[i].flg=0;
}
qsort(a,n,sizeof(Node),cmp);
for(int i=0;i<n;i++){
if(a[i].t2>=a[i].t1+now){
ans++;
now+=a[i].t1;
a[i].flg=1;
Q.push(a[i]);
}
else{
Node e=Q.top();
if(a[i].t1>e.t1)continue;
Q.pop();
now+=a[i].t1-e.t1;
a[i].flg=1;
Q.push(a[i]);
}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
