合成陨石

合成陨石

测试数据来自 wjszez/1022

问题描述:
czyz大学化学系的学生们最近发现了一种奇怪的陨石,这些陨石通过化学反应合成,会放出惊人的破坏力量。为了储存方便,化学系的学生们决定把这些陨石碎块合成一个大的陨石块。每一次合并,可以把两个陨石合成一个,放出的破坏能量是两个陨石的质量之和,而新产生的陨石质量是这两个陨石的质量之和。
为了将这次试验的破坏效果减少到最低,他们想请你帮忙,计算一下可以达到的最小破坏能量值。
例如有3个陨石碎片,质量依次为1,2,9。可以先将1、2合并,新陨石为3,放出的破坏能量为3。接着,将新陨石与原先的3合并,又得到新的陨石,质量为12,放出的破坏能量为12。所以总共放出的破坏能量=3+12=15。可以证明15为最小的破坏能量值。

数据输入:
输入包括两行,第一行是一个整数n(1<=n<=10000),表示陨石的个数。第二行包含n个整数,用一个空格分隔,第i个整数ai(1<=ai<=20000)是第i个陨石的质量。

数据输出:
输出只有一个整数,也就是最小的破坏能量值。输入数据保证这个值小于2^31。

样例输入:
3
1 2 9

样例输出:
15

数据限制:
保证30%数据,n<=1000;
保证50%数据,n<=5000;
保证100%数据,n<=10000;

信息

ID
1022
难度
10
分类
(无)
标签
递交数
1
已通过
0
通过率
0%
上传者