`

堆+++

 
阅读更多
nocow  http://www.nocow.cn/index.php/Heap_Pascal
=w= c++ 自带堆

栗子
【2235烤鸡翅】http://cojs.tk/cogs/contest/problem.php?ctid=303 
    [题解]
       对于当前的一个顾客i
          1.剩余鸡翅足够,卖给他
          2.剩余鸡翅不够,选择已卖出的人中所需鸡翅最多的人j,
            如果 鸡翅i<鸡翅j 那么替换 ,人数不变,且剩余鸡翅增加
    [代码]
   
    var
n,i,y,max,d,ren,r:longint;tot:int64;
x,que:array [0..250010]of longint;
procedure swap(x,y:longint);var i:longint;begin
i:=que[x]; que[x]:=que[y]; que[y]:=i;
end;
procedure insert(y,x:longint);begin
  que[x]:=y;
  while (x>1)and(que[x]>que[x div 2]) do
    begin
       swap(x,x div 2);
       x:=x div 2;
    end;
end;
procedure down;var i,j:longint;begin
  i:=1;
  if i*2+1<=r then
	 begin
	 if que[i*2]>que[i*2+1] then j:=i*2 else j:=i*2+1;
	 end
	 else if i*2<=r then j:=i*2 else exit;
  while que[i]<que[j] do
    begin
      swap(i,j);
      i:=j;
      if i *2+1<=r then
        begin
          if que[i*2]>que[i*2+1] then j:=i*2 else j:=i * 2+1;
        end
      else if i *2<=r then j:=i *2 else exit;
    end;
end;
begin
assign(input,'wing.in');reset(input);
assign(output,'wing.out');rewrite(output);
  read(n);
  tot:=0;  r:=0;
  for i:=1 to n do read(x[i]);
  for i:=1 to n do
    begin
      inc(tot,x[i]);
      read(y);
      if  tot>=y then
        begin
          inc(r);
          insert(y,r);
          dec(tot,y);
          inc(ren);
        end else
      begin
        if que[1]>y then 
		 begin 
		 inc(tot,que[1]-y); que[1]:=y; down; 
		 end;
      end;
    end;
write(ren);
close(input);close(output);
end.
    
分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics