现在的位置: 首页 > 综合 > 正文

poj2182

2018年01月15日 ⁄ 综合 ⁄ 共 1464字 ⁄ 字号 评论关闭

【题意】

已知每头牛左边比他名次小的牛的数量,求所有牛的名次

【输入】

第一行n

接下来n-1行描述2~n头牛左边名次比其小的牛的数量

【输出】

n行,表示各个牛的名次

线段树

每个点表示只考虑剩余牛,左边牛比当前牛名次小的数量

每次找最靠右的值为0的牛,就是当前名次的牛

然后把其右边的节点值全部减一

重复以上步骤n次就得出解

program poj2182;
var
  tot,n,i,j,k:longint;
  ans:array [0..8001] of longint;
  decr,min,left,right:array [0..200001] of longint;

procedure update (now:longint);inline;
begin
  if left[now]=0 then
    begin
      inc(tot);
      left[now]:=tot;
    end;
  if right[now]=0 then
    begin
      inc(tot);
      right[now]:=tot;
    end;
  if decr[now]<>0 then
    begin
      min[left[now]]:=min[left[now]]+decr[now];
      decr[left[now]]:=decr[left[now]]+decr[now];
      min[right[now]]:=min[right[now]]+decr[now];
      decr[right[now]]:=decr[right[now]]+decr[now];
      decr[now]:=0;
    end;
end;

function find :longint;
var
  l,r,mid,now:longint;
begin
  l:=1;
  r:=n;
  now:=0;
  while l<>r do
    begin
      update(now);
      mid:=(l+r) div 2;
      if min[right[now]]=0 then
        begin
          l:=mid+1;
          now:=right[now];
        end
                           else
        begin
          r:=mid;
          now:=left[now];
        end;
    end;
  exit(l);
end;

procedure insert (p,s,e,l,r,now:longint);
var
  mid:longint;
begin
  if (s=l)and(e=r) then
    begin
      min[now]:=min[now]+p;
      decr[now]:=decr[now]+p;
      exit;
    end;
  update(now);
  mid:=(l+r) div 2;
  if e<=mid then insert(p,s,e,l,mid,left[now])
            else
  if s>mid then insert(p,s,e,mid+1,r,right[now])
           else
    begin
      insert(p,s,mid,l,mid,left[now]);
      insert(p,mid+1,e,mid+1,r,right[now]);
    end;
  if min[left[now]]<min[right[now]] then min[now]:=min[left[now]]
                                    else min[now]:=min[right[now]];
end;

begin
  read(n);
  tot:=0;
  for i:=2 to n do
    begin
      read(k);
      insert(k,i,i,1,n,0);
    end;
  for i:=1 to n do
    begin
      k:=find;
      ans[k]:=i;
      if k<n then insert(-1,k+1,n,1,n,0);
      insert(100000,k,k,1,n,0);
    end;
  for i:=1 to n do
    writeln(ans[i]);
end.
【上篇】
【下篇】

抱歉!评论已关闭.