JSOI2007建筑抢修

时间:2023-03-08 18:32:13

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

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

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

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

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

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

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

代码:

 var  i,n,cnt,time:longint;
p,t,a:array[..] of longint;
procedure put(x:longint);
var i,k:longint;
begin
inc(cnt);
i:=cnt;k:=i>>;
while k>= do
begin
if a[k]<x then begin a[i]:=a[k];i:=k;k:=k>>;end
else k:=;
end;
a[i]:=x;
end;
procedure get(x:longint);
var i,k:longint;
begin
i:=;k:=i<<;
while k<=cnt do
begin
if (k<cnt) and (a[k+]>a[k]) then inc(k);
if a[k]>x then begin a[i]:=a[k];i:=k;k:=k<<;end
else k:=cnt+;
end;
a[i]:=x;
end;
procedure sort(h,l:longint);
var i,j,x,y,temp:longint;
begin
i:=h;j:=l;x:=p[(i+j)>>];y:=t[(i+j)>>];
repeat
while (p[i]<x) do inc(i);
while (p[j]>x) do dec(j);
if i<=j then
begin
temp:=p[i];p[i]:=p[j];p[j]:=temp;
temp:=t[i];t[i]:=t[j];t[j]:=temp;
inc(i);dec(j);
end;
until i>j ;
if i<l then sort(i,l);
if j>h then sort(h,j);
end;
procedure init;
begin
readln(n);
for i:= to n do readln(t[i],p[i]);
sort(,n);
end;
procedure main;
begin
time:=;
cnt:=;
for i:= to n do
begin
if time+t[i]<=p[i] then
begin
put(t[i]);inc(time,t[i]);continue;
end;
if (time-a[]+t[i]<=p[i]) and (t[i]<a[]) then
begin
inc(time,t[i]-a[]);get(t[i]);continue;
end;
end;
writeln(cnt);
end;
begin
init;
main;
end.