bzoj2151: 种树(双向链表+堆)

题目大意：n个数围成一个圈，选了某个数就不能选它相邻的两个数，问选m个数，最大值为多少。

先用堆维护n个数的最大值，每次取出最大值加进答案，选了某个数之后有可能选它相邻的两个比他更优，所以把旁边的两个数删掉，把这次选的数的值改成左边的数+右边的数-这次选的数，如果下次取了这个数相当于不选这个数换成另外两个，选择m次就是取了m个数。一个数的左右两边的数就用双向链表来搞就行了。

代码如下：

var
  n,m,x,i,ans:longint;
  l,r,heap,pos,a:array[0..200001]of longint;
 
procedure down(i:longint);
var
  t,j:longint;
begin
  while (i<<1<=n) do
  begin
    if (i<<1=n)or(a[heap[i<<1]]>a[heap[i<<1 or 1]]) then j:=i<<1
    else j:=i<<1 or 1;
    if a[heap[i]]<a[heap[j]] then
    begin
      t:=heap[i];heap[i]:=heap[j];heap[j]:=t;
      t:=pos[heap[i]];pos[heap[i]]:=pos[heap[j]];pos[heap[j]]:=t;
      i:=j;
    end
    else exit;
  end;
end;

procedure up(i:longint);
var
  t:longint;
begin
  while i>1 do
  begin
    if a[heap[i]]>a[heap[i>>1]] then
    begin
      t:=heap[i];heap[i]:=heap[i>>1];heap[i>>1]:=t;
      t:=pos[heap[i]];pos[heap[i]]:=pos[heap[i>>1]];pos[heap[i>>1]]:=t;
      i:=i>>1;
    end
    else exit;
  end;
end;
 
begin
  readln(n,m);
  if (m>n>>1) then writeln('Error!')
  else
  begin
    for i:=1 to n do
    begin
      read(a[i]);
      l[i]:=i-1;r[i]:=i+1;heap[i]:=i;pos[i]:=i;up(i);
    end;
    l[1]:=n;r[n]:=1;
    for i:=1 to m do
    begin
      x:=heap[1];inc(ans,a[x]);
      a[x]:=a[l[x]]+a[r[x]]-a[x];down(pos[x]);
      a[l[x]]:=-maxlongint;down(pos[l[x]]);l[x]:=l[l[x]];
      a[r[x]]:=-maxlongint;down(pos[r[x]]);r[x]:=r[r[x]];
      l[r[x]]:=x;r[l[x]]:=x;
    end;
    writeln(ans);
  end;
end.

View Code

PS：我才知道堆可以这么拿来删元素QAQ