合并果子
时间限制: 10000ms内存限制: 65536kB
描述
在一个果园里,多多已经将所有的果子打了下来,而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。
因为还要花大力气把这些果子搬回家,所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为1,并且已知果子的种类数和每种果子的数目,你的任务是设计出合并的次序方案,使多多耗费的体力最少,并输出这个最小的体力耗费值。
例如有3种果子,数目依次为1,2,9。可以先将1、2堆合并,新堆数目为3,耗费体力为3。接着,将新堆与原先的第三堆合并,又得到新的堆,数目为12,耗费体力为12。所以多多总共耗费体力=3+12=15。可以证明15为最小的体力耗费值。
输入
输入文件fruit.in包括两行,第一行是一个整数n(1<=n<=10000),表示果子的种类数。第二行包含n个整数,用空格分隔,第i个整数ai(1<=ai<=20000)是第i种果子的数目。
输出
输出文件fruit.out包括一行,这一行只包含一个整数,也就是最小的体力耗费值。输入数据保证这个值小于231。
样例输入
3
1 2 9
样例输出
15
提示
对于30%的数据,保证有n<=1000: 对于50%的数据,保证有n<=5000; 对于全部的数据,保证有n<=10000。
参考代码
分享到:
相关推荐
合并果子(NOIP2004TG_2)快排+插入
合并果子源代码
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花...
每一次合并,多多可以把两堆果子合并到一起,消耗的体力等于两堆果子的重量之和。可以看出,所有的果子经过n-1次合并之后,就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。 因为还要花...
这个是编程的贪心算法简单运用,可以试着理解理解。。
合并果子.md
果子合并(ACM/ICPC训练题): 有四堆果子, 其数量分别是:10, 30, 15和100,试设计一种最佳方案,将果子合并为一堆,使得合并工作量最小。 注:规定合并两堆果子的工作量是这两堆果子的数量之和。 哈夫曼树及其应用...
学生籍贯信息记录簿设计 编制一个学生籍贯信息记录簿,每个学生信息包括:学号、姓名、籍贯。具体功能: (1)创建学生信息并以磁盘文件保存; (2)读取磁盘文件并显示输出所有学生的籍贯信息;...
java设计模式【之】装饰者模式【源码】【场景:煎饼果子+肠+蛋】 * 测试类【之】煎饼果子来一套 * * 不改变原有对象的基础上,强化已经存在的功能 * 被装饰者与装饰者实现同一个抽象或接口 * 装饰后,最终还是...
学生成绩记录簿设计 编制一个C语言成绩记录簿,每个学生信息包括:学号、姓名、C语言成绩。具体功能: (1)创建学生信息并以磁盘文件保存; (2)读取磁盘文件并显示输出所有学生的成绩; (3)按学号或姓名查询...
JAVA实验1-4
学生选修课程系统设计 假定有n门课程,每门课程有:课程编号,课程名称, 课程性质(公共课、必修课、选修课),总学时,授课学时, 实验或上机学时,学分,开课学期等信息,学生可按要求 (如总学分不得少于60)自由...
幼儿园教案2021-中班音乐:摘果子.doc
幼儿园教案2021-中班数学:摘果子.doc
一款免费的期货程序化跟单人家,性能卓越 主要特色有: 1、正反向跟单 2、按比例跟单 3、限定品种合约跟单 4、跨期货公司平台多账户跟单 5、一跟多 6、多跟一 7、多跟多 8、实盘跟模拟 9、实盘跟实盘 10、...
幼儿园教案2021-中班科学:秋天果子多.doc
网上书店 实现查询功能 前端界面:使用Jquery+bootstrap搭建,响应式布局 后台:使用JSP+Servlet MVC模式搭建
煎饼果子登录器 suv新款车广汽Acura CDX Sport Hybrid 超凡科技 自.. 广汽Acura高端动能混动SUV CDX 作为首批达到“国六”标准,搭载2.0L i-MMD混合动力,兼具高效与低耗,超乎寻常的静谧空间,让驾驭感从此步入崭新...
建筑施工组织2021-G045线果子沟口至霍尔果斯高速公路2标施工组织设计.doc