记录编号	11245	评测结果	AWWWWWWWWW
题目名称	[NOIP 2004]合并果子	最终得分	10
用户昵称	rottenwood	是否通过	未通过
代码语言	Pascal	运行时间	0.928 s
提交时间	2009-07-19 11:23:51	内存使用	0.15 MiB

program fruit;
var
s:array[1..10000] of longint;
i,j,m,n,c,t1,t2,new,tot,l,r,temp:longint;
flag:boolean;
procedure qsort(l,r:longInt);
var
  i,j,x,y,y1:longint;
begin
  i:=l; j:=r; x:=s[(l+r) div 2];
  repeat
    while s[i]<x do i:=i+1;
    while x<s[j] do j:=j-1;
    if i<=j then
    begin
      y:=s[i]; s[i]:=s[j];s[j]:=y;
      i:=i+1; j:=j-1;
    end;
  until i>j;
  if l<j then qsort(l,j);
  if i<r then qsort(i,r);
end;
begin
assign(input,'fruit.in');reset(input);
assign(output,'fruit.out');rewrite(output);
readln(n);
for i:=1 to n do read(s[i]);
qsort(1,n);
c:=n;
while s[2]<>0 do begin
t1:=s[1]; t2:=s[2];
new:=t1+t2;
inc(tot,new);
l:=1; r:=c-2;
c:=c-2;
if c<1 then begin writeln(tot); close(output); halt; end else begin
for i:=1 to c do s[i]:=s[i+2];s[c+1]:=0;s[c+2]:=0;  end;
 while l<=r  do begin
  if new=s[(l+r) div 2] then begin temp:=(l+r) div 2; break;end;
  if new<s[(l+r) div 2] then r:=((l+r) div 2)-1
                         else l:=((l+r) div 2)+1;
{if l=r then begin for i:=c+1 downto r+1 do s[i]:=s[i-1]; s[r]:=new;inc(c); end;}
 if l>r then begin for i:=c downto l do  s[i+1]:=s[i];
 s[l]:=new; inc(c); end; end;
 end;
writeln(tot);
close(output);
end.