不是VIP会员,不能显示答案

题目解答

题目:
合并礼物
【问题描述】
圣诞节快到了,圣诞老人又要开始忙起来了,和往年一样,圣诞老人要在礼物乐园里挑选礼物送给小朋友们。
在礼物乐园,圣诞老人挑选好礼物后,把礼物按照不同的种类分成了不同的堆,现在,圣诞老人决定把所有的礼物合成一堆。
每一次合并,圣诞老人可以把两堆礼物合并到一起,消耗的体力等于两堆礼物的重量之和。可以看出,所有的礼物经过n-1次合并之后,就只剩下一堆了。圣诞老人在合并礼物时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些礼物搬到他的鹿车,所以圣诞老人在合并礼物时要尽可能地节省体力。假定每个礼物重量都为1,并且已知礼物的种类和每种礼物的数目,你的任务是设计出合并的次序方案,使圣诞老人耗费的体力最小,并输出这个最小的体力耗费值。
例如有3种礼物,数目依次为1,2,9。可以先将 1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为 12。所以圣诞老人总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。

【输入】
输入包括两行,第一行是一个整数n(1 <= n <= 100),表示礼物的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1 <= ai <= 100)是第i种礼物的数目。

【输出】
输出包括一行,这一行只包含一个整数,也就是最小的体力耗费值。

【样例输入】
3
1 2 9

【样例输出】
15

【解题思路】
首先将所有的礼物堆按照每堆礼物的数目进行排序,将数目最少的两堆礼物合并,然后再将新堆放入数列中重新排序,再取出最少数目的两堆合并……每次合并后将体力消耗值加入到total变量,依次类推,经过n-1次合并后,所有礼物都合并成了一堆,total即为问题所求的“最小的体力耗费值”。

请完善以下程序:
program test06;
var
  n,i,j,total:longint;
  a:array[0..101] of longint;
procedure qsort(l,r:longint);
var
  i,j,x,temp:longint;
begin
  i:=l;
  j:=r;
  x:=a[(i+j) shr 1];
  repeat
    while a[i]<x do inc(i);
    while x<a[j] do dec(j);
      if i<=j then begin
        temp:=a[i];
           a[i]:=a[j]  ;
        a[j]:=temp;
        i:=i+1;
           dec(j) ;
               end;
  until i<=j ;
  if l<j then qsort(l,j);
  if i<r then  qsort(i,r)  ;
end;
begin
  readln(n);
  for i:=1 to n do
    read(a[i]);
    qsort(1,n)
     total:=0   ;
  for i:=1 to n-1 do begin
    inc(total,a[i]+a[i+1]);
    a[i+1]:=a[i]+a[i+1];
      qsort(1,n)   ;
  end;
  writeln(total);
end.
考点:
分析:
解答:
评论:
老师: