首页 > 代码库 > 1029: [JSOI2007]建筑抢修
1029: [JSOI2007]建筑抢修
1029: [JSOI2007]建筑抢修
Time Limit: 4 Sec Memory Limit: 162 MBSubmit: 2382 Solved: 1033
[Submit][Status]
Description
小刚在玩JSOI提供的一个称之为“建筑抢修”的电脑游戏:经过了一场激烈的战斗,T部落消灭了所有z部落的入侵者。但是T部落的基地里已经有N个建筑设施受到了严重的损伤,如果不尽快修复的话,这些建筑设施将会完全毁坏。现在的情况是:T部落基地里只有一个修理工人,虽然他能瞬间到达任何一个建筑,但是修复每个建筑都需要一定的时间。同时,修理工人修理完一个建筑才能修理下一个建筑,不能同时修理多个建筑。如果某个建筑在一段时间之内没有完全修理完毕,这个建筑就报废了。你的任务是帮小刚合理的制订一个修理顺序,以抢修尽可能多的建筑。
Input
第一行是一个整数N,接下来N行每行两个整数T1,T2描述一个建筑:修理这个建筑需要T1秒,如果在T2秒之内还没有修理完成,这个建筑就报废了。
Output
输出一个整数S,表示最多可以抢修S个建筑。 数据范围: N<150000,T1
Sample Input
4
100 200
200 1300
1000 1250
2000 3200
100 200
200 1300
1000 1250
2000 3200
Sample Output
3
HINT
Source
题解:啊啊啊啊啊又脑抽了(phile:我竟无言以对了 HansBug:唉,这就是搞了一星期吴仲华杯的后果)唉。。手生了没办法——珍爱生命,远离吴仲华杯(HansBug:反正再也没有了= =)!!!23333。。。好了思路——这是一个经典的贪心问题先按照deadline从小到大排序,然后每次保留一个当前消耗时间,假如已经消耗的时间+当前任务用时<=当前任务deadline的话,那就直接加进来;假如已消耗时间+当前任务用时>当前任务deadline的话,那检查一下当前任务耗时是否不比任何一次之前进行的任务都大,如果不是的话加进来,并把之前那个最大的扔出去;否则凉拌。。。(由于N<=150000,所以建议用大根堆维护,本萌妹还是继续用我萌萌哒左偏树,mua~~)
1 var 2 i,j,k,m,n,head:longint; 3 l:int64; 4 a,lef,rig,fix,b,c,d:array[0..200000] of longint; 5 function min(x,y:longint):longint;inline; 6 begin 7 if x<y then min:=x else min:=y; 8 end; 9 function max(x,y:longint):longint;inline;10 begin11 if x>y then max:=x else max:=y;12 end;13 procedure swap(var x,y:longint);inline;14 var z:longint;15 begin16 z:=x;x:=y;y:=z;17 end;18 procedure sort(l,r:longint);inline;19 var i,j,x,y:longint;20 begin21 i:=l;j:=r;22 x:=c[(i+j) div 2];23 repeat24 while c[i]<x do inc(i);25 while c[j]>x do dec(j);26 if i<=j then27 begin28 swap(c[i],c[j]);29 swap(d[i],d[j]);30 inc(i);dec(j);31 end;32 until i>j;33 if l<j then sort(l,j);34 if i<r then sort(i,r);35 end;36 procedure merge(var x,y:longint);inline;37 begin38 if x=0 then swap(x,y);39 if y=0 then exit;40 if a[x]<a[y] then swap(x,y);41 merge(rig[x],y);42 fix[x]:=max(fix[lef[x]],fix[rig[x]])+1;43 if fix[lef[x]]<fix[rig[x]] then swap(lef[x],rig[x]);44 end;45 procedure cuthead(var head:longint);inline;46 begin47 if head=0 then exit;48 merge(lef[head],rig[head]);49 head:=lef[head];50 end;51 begin52 readln(n);53 for i:=1 to n do readln(d[i],c[i]);54 sort(1,n);l:=0;55 head:=0;m:=0;k:=0;56 fillchar(a,sizeof(a),0);57 fillchar(lef,sizeof(lef),0);58 fillchar(rig,sizeof(rig),0);59 fillchar(fix,sizeof(fix),0);60 for i:=1 to n do61 begin62 if int64(l+int64(d[i]))<=int64(c[i]) then63 begin64 l:=int64(l+int64(d[i]));inc(k);65 inc(m);a[m]:=d[i];66 j:=m;merge(head,j);67 end68 else69 begin70 if (int64(d[i])<int64(a[head])) then71 begin72 l:=int64(l+int64(d[i])-int64(a[head]));73 inc(m);a[m]:=d[i];74 cuthead(head);j:=m;75 merge(head,j);76 end;77 end;78 end;79 writeln(k);80 readln;81 end.82
1029: [JSOI2007]建筑抢修
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。