8
22
2015
0

[BZOJ1029] [JSOI2007] 建筑抢修

大家好,我是传奇蒟蒻!

刚刚玩了一下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;
}
Category: BZOJ | Tags: OI | Read Count: 505

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com