首先容易知道,最后一个数是最容易确定的,于是从后往前确定
对于位置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)虽然慢了一点,但是编程复杂度大大下降