记录编号	1083	评测结果	AAAAAAAAAA
题目名称	[NOIP 2004]合并果子	最终得分	100
用户昵称	zpl123	是否通过	通过
代码语言	Pascal	运行时间	0.082 s
提交时间	2008-07-23 21:54:22	内存使用	0.19 MiB

program fruit;
var
a,b:array[1..10000] of longint;
i,i1,j1,key,k,n,head,tail:longint;
total:longint;

procedure quicksort(start,final:integer);
 begin
 if start>=final then exit;
 k:=random(final-start)+start;
 i1:=start-1;j1:=final+1;
 for i:=start to final do
 if a[i]<a[k] then
 begin
 inc(i1);
 b[i1]:=a[i];
 end
 else if (i<>k) then
 begin
 dec(j1);
 b[j1]:=a[i];
 end;
 b[i1+1]:=a[k];
 for i:=start to final do a[i]:=b[i];
 quicksort(start,i1);
 quicksort(j1,final);
 end;

 begin
  assign(input,'fruit.in');
  reset(input);
  assign(output,'fruit.out');
  rewrite(output);
  fillchar(a,sizeof(a),0);
  fillchar(b,sizeof(b),0);
  read(n);
  for i:=1 to n do read(a[i]);
  if n=1 then begin writeln(a[1]);halt;end;
  if n=2 then begin writeln(a[1]+a[2]);halt;end;
  quicksort(1,n);
  fillchar(b,sizeof(b),0);
  i1:=3;head:=1;tail:=1;b[1]:=a[1]+a[2];total:=b[1];
  repeat
   if a[i1]>=b[head] then
   begin
   if (b[head+1]<>0) and (b[head+1]<=a[i1]) then
    begin
    inc(tail);
    b[tail]:=b[head]+b[head+1];
    inc(head,2);
    total:=total+b[tail];
    end
    else
    begin
    inc(tail);
    b[tail]:=b[head]+a[i1];
    total:=total+b[tail];
    inc(i1);inc(head);
    end;
    end
    else
    begin
    if (i1=n) then
    begin
    inc(tail);
    b[tail]:=b[head]+a[i1];
    total:=total+b[tail];
    inc(i1);inc(head);
    end
    else
    begin
    if a[i1+1]<=b[head] then
    begin
    inc(tail);
    b[tail]:=a[i1]+a[i1+1];
    inc(i1,2);
    total:=total+b[tail];
    end
    else
    begin
    inc(tail);
    b[tail]:=a[i1]+b[head];
    inc(i1);inc(head);
    total:=total+b[tail];
    end;
    end;
    end;
  until i1=n+1;
  for i:=head to tail do
   a[i]:=b[i];
   quicksort(head,tail);
  for i:=head to tail do
   b[i]:=a[i];
  while head<tail do
   begin
    inc(tail);
    b[tail]:=b[head]+b[head+1];
    total:=total+b[tail];
    inc(head,2);
   end;
 writeln(total);
close(input);
close(output);
end.