POJ/3253.pas

   1 const
   2   maxn=20010;
   3
   4 var
   5   heap:array [0..maxn] of longint;
   6   n,m,i,tmp:longint;
   7   ans:int64;
   8
   9 procedure swap(var p,q:longint);
  10 begin
  11   p:=p xor q;
  12   q:=p xor q;
  13   p:=p xor q;
  14 end;
  15
  16 procedure up(i:longint);
  17 begin
  18   if i=1 then exit;
  19   if heap[i]<heap[i shr 1] then
  20     begin
  21       swap(heap[i],heap[i shr 1]);
  22       up(i shr 1);
  23     end;
  24 end;
  25
  26 procedure down(i:longint);
  27 var
  28   j:longint;
  29
  30 begin
  31   j:=i shl 1;
  32   if j>n then exit;
  33   if (j+1<=n) and (heap[j+1]<heap[j]) then inc(j);
  34   if heap[i]>heap[j] then
  35     begin
  36       swap(heap[i],heap[j]);
  37       down(j);
  38     end;
  39 end;
  40
  41 function delmin:longint;
  42 begin
  43   delmin:=heap[1];
  44   heap[1]:=heap[n];
  45   dec(n);
  46   down(1);
  47 end;
  48
  49 begin
  50   readln(m);
  51   n:=m;
  52   for i:=1 to m do read(heap[i]);
  53   for i:=m shr 1 downto 1 do down(i);
  54   for i:=2 to m do
  55     begin
  56       tmp:=delmin+delmin;
  57       inc(ans,tmp);
  58       inc(n);
  59       heap[n]:=tmp;
  60       up(n);
  61     end;
  62   writeln(ans);
  63 end.