gggs 新万博体育manbetx|新万博体育|万博manbetx登录  
阳光一小
您现在的位置: 南城区阳光第一小学 >> 栏目导航 >> 学生天地 >> 电脑博士 >> 程序设计 >> 提高测试题 >> 文章正文 今天是:
合并果子
作者:佚名    文章来源:本站原创    点击数:2003    更新时间:2014/11/17    
        ★★★ 【字体:

合并果子:

      [问题描述]

      在一个果园里,多多已经将所有的果子打下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合并成一堆。

      每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子是总共消耗的体力等于每次合并所消耗体力之和。

      因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多消耗的体力最少,并输出这个最小的体力消耗值。

      例如有3种果子,数目依次为129,可以先将12堆合并,新堆数目为3,消耗体力为3。接着,将新堆与原先的第三堆合并,又得到新堆,数目为12,消耗体力为12。所以多多总共消耗的体力=3+12=15。可以证明15为最小的体力消耗值。

      [输入文件]

      输入文件fruit.in包括两行,第一行是一个整数n1<=n<=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,第I个整数ai1<=ai<=20000)是第I种果子的数目。

      [输出文件]

      输出文件fruit.out包括一行,这一行只包含一个整数,也就是最小的体力消费值。输入数据保证这个值小于231

      [样例输入]

      3

      1 2 9

      [样例输出]

      15

      

      解题报告:

      该问题是比较简单的动态规划问题,甚至可以不考虑动态规划,算法很简单。由于题目中要求输入的数据保证最后消耗体力值小于231,而且nai都作了限制,特别临竞赛前将数据n的值由1<=n<=30000修改为1<=n<=10000,所以不涉及高精度运算。这道题相对简单,只要设置一个一维数组记录每种果子的个数,在该数组中找到两个最小的元素min1:=a[i1]min2:=a[i2],然后将它们的和赋予a[i1],并把a[i2]设置为无穷大来表示此种果子已经被合并。并且在该数组中继续寻找min1min2,重复以上操作,就可以得出体力消耗总量的最小值。

      下面给出我写的一个参考程序,该程序已经在官方给出的测试数据中全部通过,但有些数据可能会超时:

 

      const

      oo=200000000;

      maxn=10000;

      var

      a:array[1..maxn] of longint;

      n,i,j,k1,k2:integer;

      total,min1,min2:longint;

      begin

      readln(n);

      for i:=1 to n do read(a[i]);

      total:=0;

      for j:=1 to n-1 do

      begin

      min1:=oo;

      min2:=oo;

      for i:=1 to n do

         if (a[i]<>oo) and ((a[i]       if a[i]          else if a[i]>=min1 then

      begin min2:=a[i];k2:=i end;

      a[k1]:=min1+min2;

      a[k2]:=oo;

      total:=total+a[k1]

      end;

      writeln(total)

end.

文章录入:admin    责任编辑:admin 
  • 上一篇文章:

  • 下一篇文章: 没有了
  • 发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口
    网友评论:(只显示最新10条。评论内容只代表网友观点,与本站立场无关!)

    粤公网安备 44190002000253号