poj2828

很容易想到一种动态的做法:平衡树……

或者是二分+树状数组

但,前者编程复杂度较大,而且据说会被卡(没试过);后者理论上超时(据说可以擦边过?);

所以要尝试新的算法;

倒着考虑,显然最后一个对象的位置是最容易确定,顺带着,容易发现,

在第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.
上一篇:csuoj 1353: Guessing the Number


下一篇:tokudb引擎磁盘空间不足导致写入失败的调查