记录编号	5065	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	Hamster	是否通过	通过
代码语言	Pascal	运行时间	0.106 s
提交时间	2008-10-24 19:26:58	内存使用	0.15 MiB

program fruit; 
const 
  maxn=10000; 
type 
  data=array[1..maxn] of longint; 
var 
  fin,fout:text; 
  min1,min2,ans:longint; 
  m,n,i:integer; 
  tr:data; 

procedure init; 
var 
  i:integer; 
begin 
  fillchar(tr,sizeof(tr),0); 
  ans:=0; 
  assign(fin,'fruit.in'); 
  assign(fout,'fruit.out'); 
  reset(fin); 
  readln(fin,n); 
  
  m:=n; 
  for i:=1 to n do 
  read(fin,tr[i]); 
  close(fin); 
end; 

{----------------------------} 

procedure heap(var a:data;n:integer;i:integer); 
var 
  x:longint; 
  k:integer; 
begin 
  x:=a[i]; 
  k:=2*i; 
  while k<=n do 
  begin 
    if (k<n)and(a[k]>a[k+1]) then k:=k+1; 
    if x>a[k] then 
    begin 
      a[i]:=a[k]; 
      i:=k; 
      k:=2*i; 
    end 
    else break; 
  end; 
  a[i]:=x; 
end; 

{----------------------------} 

procedure insert(x:longint); 
var 
  i:integer; 
begin 
  n:=n+1; 
  tr[n]:=x; 
  i:=n; 
  while (i>1)and(x<tr[i div 2]) do 
  begin 
    tr[i]:=tr[i div 2]; 
    i:=i div 2; 
  end; 
  tr[i]:=x; 
end; 

{----------------------------} 

function delmin:longint; 
begin 
  delmin:=tr[1]; 
  tr[1]:=tr[n]; 
  n:=n-1; 
  heap(tr,n,1); 
end; 

begin 
  init; 
  for i:=(n div 2)downto 1 do heap(tr,n,i);  
  for i:=1 to m-1 do 
  begin 
    min1:=delmin; 
    min2:=delmin; 
    insert(min1+min2); 
    ans:=ans+min1+min2; 
  end; 
  rewrite(fout); 
  write(fout,ans); 
  close(fout); 
end.