很容易想到一种动态的做法:平衡树……
或者是二分+树状数组
但,前者编程复杂度较大,而且据说会被卡(没试过);后者理论上超时(据说可以擦边过?);
所以要尝试新的算法;
倒着考虑,显然最后一个对象的位置是最容易确定,顺带着,容易发现,
在第i个人后插入,就是在当前队列中前面有i个空位的空位置;
于是还是可以用平衡数……
当然更简单快捷的方法是线段树,每个节点表示这个区间还有的空位数;
然后类比平衡树的查找k大,很快就能写成
var tree:array[..] of longint;
p,a,w:array[..] of longint;
n,i:longint; procedure build(i,l,r:longint);
var m:longint;
begin
tree[i]:=r-l+;
m:=(l+r) shr ;
if l<>r then
begin
build(i*,l,m);
build(i*+,m+,r);
end;
end; function ask(i,l,r,k:longint):longint;
var m:longint;
begin
if l=r then
begin
tree[i]:=;
exit(l);
end;
m:=(l+r) shr ;
if tree[i*]>k then
begin
dec(tree[i*]); //在查找的过程中顺便把区间空位数更新
exit(ask(i*,l,m,k));
end
else begin
dec(tree[i*+]);
exit(ask(i*+,m+,r,k-tree[i*])); //有没有觉得很平衡树找区间k值神似
end;
end; begin
while not eoln do
begin
readln(n);
fillchar(tree,sizeof(tree),);
build(,,n);
for i:= to n do
readln(p[i],a[i]);
for i:=n downto do
w[i]:=ask(,,n,p[i]); //w代表每个点的位置
for i:= to n do
p[w[i]]:=a[i];
for i:= to n do
begin
write(p[i]);
if i<>n then write(' '); //注意别PE了
end;
writeln;
end;
end.