合并果子问题pascal

我的想法是:从小到大排序 加合前面2个,不断循环

但是和答案差一点 谁帮我看看..

type
        int=longint;
var
        n,s,i,k,last:int;
        ai:array[1..20000]of int;

procedure qsort(l,r:int);
var
        i,j,mid,k:int;
begin
        i:=l; j:=r; mid:=ai[random(r-l)+l];
        repeat
                while ai[i]<mid do inc(i);
                while ai[j]>mid do dec(j);
                if i<=j then
                begin
                        k:=ai[i];
    ai[i]:=ai[j];
   ai[j]:=k;
                        inc(i); dec(j);
                end;
        until i>j;
 if i<r then qsort(i,r);
        if j>l then qsort(l,j);
end;

begin
        assign(input,'p1066.in');reset(input);
        assign(output,'p1066.out');rewrite(output);
        readln(n);
        for i:=1 to n do
        read(ai[i]);
        last:=n;

        for i:=1 to n do
        begin
                qsort(1,last);
                ai[2]:=ai[1]+ai[2];
                ai[1]:=0;
                k:=ai[last];
                ai[last]:=ai[1];
                ai[1]:=k;
                dec(last);
                s:=s+ai[2];
        end;

        writeln(s);
        close(input);close(output);
end.

你每次都快排，时间复杂度太高，会超时。

不过你的思路是对的，但要用堆排来实现。

var
 x,y,i,j,k,m,n,t:longint;ans:int64;
 a:array[1..20000]of longint;

procedure work(i,n:longint);
var j,t:longint;
begin
 j:=i*2;
 while j<=n do
  begin
   if (j<n)and(a[j]>a[j+1]) then j:=j+1;
   if a[j]<a[i] then
    begin
    t:=a[i];a[i]:=a[j];a[j]:=t;
    i:=j;j:=i*2;
    end else exit;
  end;
end;

begin
 readln(n);m:=n;
 for i:=1 to n do read(a[i]);
 for i:= (n div 2) downto 1 do work(i,n);

 for k:=1 to n-1 do
  begin
   x:=a[1];a[1]:=a[m]; work(1,m-1);dec(m);
   y:=a[1];a[1]:=x+y;  work(1,m);
   ans:=x+y+ans;
  end;

 writeln(ans);
end.

你的想法不错，但方法不行。

第一次用快排，以后用插排，不能用快排，不用堆排都可以。

具体程序如下算法：

var   a:array[0..15000] of longint;   i,j,n,k,tem,ans:longint; procedure sort(l,r:longint); var   i,j,x,y: longint; begin   i:=l;   j:=r;   x:=a[(l+r) div 2];   repeat     while a[i]<x do     i:=i+1;     while x<a[j] do     j:=j-1;     if not(i>j) then     begin     y:=a[i];     a[i]:=a[j];     a[j]:=y;     inc(i);     j:=j-1;     end;   until i>j;   if l<j then     sort(l,j);   if i<r then     sort(i,r); end; begin   assign(input,'T4.in');reset(input);   assign(output,'T4.out');rewrite(output);   readln(n);   for i:=1 to n do read(a[i]);   sort(1,n);   ans:=0;   i:=1;   while i<n do   begin     tem:=a[i]+a[i+1];     ans:=ans+tem;     j:=n;     while a[j]>tem do j:=j-1;     for k:=i to j do     a[k-1]:=a[k];     a[j]:=tem;     i:=i+1;   end;   writeln(ans);   close(input);close(output); end.

tyvj的题目吧，大概是超时了吧，只能过几个点。你每次都快排，时间复杂度太高，每次改变的量都是ai[2],ai[1]，不如把ai[2]插入，不过整个要动一动。每次去除ai[i]，使ai[i+1]:=a[i+1]+a[i];从ai[i+2]向后搜，找到ai[i+1]的新位置，插入，其余前移一位，这样可以节约不少时间，当然用链表来做插入更方便