首页 > 代码库 > JSOI2007建筑抢修

JSOI2007建筑抢修

2024-07-09 01:11:41   222人阅读

实际上和大多这类题一样（比如wikioi上的地鼠游戏），考察的都是堆的操作

这次改完之后就算把堆的模版定下来了

悲剧的是：大根堆打成了小根堆，导致一开始一直是10分……

按结束时间排序，（经过验证，结束时间相同的建筑不需要在根据t的大小来排序）

如果time+t[i]<=p[i] 那么直接将它加入堆中

如果上面的条件不满足，取出堆中的最大元素，如果time-a[1]+t[i]<=p[i] 那么将a[1]替换为t[i]

这样是因为这使得总完成任务数没变，但总时间却缩小了，不会比原来的决策差

代码：

 1 var  i,n,cnt,time:longint; 2      p,t,a:array[0..200000] of longint; 3 procedure put(x:longint); 4  var i,k:longint; 5  begin 6    inc(cnt); 7    i:=cnt;k:=i>>1; 8    while k>=1 do 9     begin10       if a[k]<x then begin a[i]:=a[k];i:=k;k:=k>>1;end11       else k:=0;12     end;13    a[i]:=x;14  end;15 procedure get(x:longint);16  var i,k:longint;17  begin18    i:=1;k:=i<<1;19    while k<=cnt do20     begin21       if (k<cnt) and (a[k+1]>a[k]) then inc(k);22       if a[k]>x then begin a[i]:=a[k];i:=k;k:=k<<1;end23       else k:=cnt+1;24     end;25    a[i]:=x;26  end;27 procedure sort(h,l:longint);28  var i,j,x,y,temp:longint;29  begin30    i:=h;j:=l;x:=p[(i+j)>>1];y:=t[(i+j)>>1];31    repeat32      while (p[i]<x) do inc(i);33      while (p[j]>x) do dec(j);34      if i<=j then35       begin36         temp:=p[i];p[i]:=p[j];p[j]:=temp;37         temp:=t[i];t[i]:=t[j];t[j]:=temp;38         inc(i);dec(j);39       end;40    until i>j ;41    if i<l then sort(i,l);42    if j>h then sort(h,j);43  end;44 procedure init;45  begin46    readln(n);47    for i:=1 to n do readln(t[i],p[i]);48    sort(1,n);49  end;50 procedure main;51  begin52    time:=0;53    cnt:=0;54    for i:=1 to n do55     begin56       if time+t[i]<=p[i] then57         begin58           put(t[i]);inc(time,t[i]);continue;59         end;60       if (time-a[1]+t[i]<=p[i]) and (t[i]<a[1]) then61         begin62           inc(time,t[i]-a[1]);get(t[i]);continue;63         end;64     end;65    writeln(cnt);66  end;67 begin68   init;69   main;70 end.
View Code

 


联系
我们