poj2182

时间:2023-12-22 22:54:56

首先容易知道,最后一个数是最容易确定的,于是从后往前确定

对于位置j,它的数就是1~n中剩余数的第a[j]+1小的数

这当然可以用平衡数做,复杂度为O(nlogn)

有没有更简洁得算法?树状数组+二分

 var v:array[..] of boolean;
    c,ans,a:array[..] of longint;
    i,j,n:longint;
function lowbit(x:longint):longint;
  begin
    exit(x and (-x));
  end; function sum(x:longint):longint;
  begin
    sum:=;
    while x> do
    begin
      sum:=sum+c[x];
      x:=x-lowbit(x);
    end;
  end; function kth(t:longint):longint;
  var l,r,m,p:longint;
  begin
    l:=;
    r:=n;
    while l<=r do
    begin
      m:=(l+r) shr ;
      p:=sum(m);       //统计二分得到的这个数前面有几个比它小的
      if (p=t) and not v[m] then exit(m);   //注意不要忘记判断这个数是否存在
      if p<t then l:=m+ else r:=m-;
    end;
  end; procedure add(x,w:longint);
  begin
    while x<=n do
    begin
      c[x]:=c[x]+w;
      x:=x+lowbit(x);
    end;
  end; begin
  readln(n);
  for i:= to n do
    readln(a[i]);
  for i:= to n do    //初始化
    add(i,);
  fillchar(v,sizeof(v),false);
  for i:=n downto do
  begin
    ans[i]:=kth(a[i]+);  //确定当前位置
    v[ans[i]]:=true;      //删除这个数
    add(ans[i],-);
  end;
  for i:= to n do
    writeln(ans[i]);
end.

总的复杂度为O(n*logn*logn)虽然慢了一点,但是编程复杂度大大下降