51nod Huffman算法

51nod Huffman算法

​​<= L1,L2,…,LN <= 1000，且均为整数）个长度单位。我们认为切割时仅在整数点处切且没有木材损失。

木匠发现，每一次切割花费的体力与该木棒的长度成正比，不妨设切割长度为1的木棒花费1单位体力。例如：若N=3，L1 = 3,L2 = 4,L3 = 5，则木棒原长为12，木匠可以有多种切法，如：先将12切成3+9.，花费12体力，再将9切成4+5，花费9体力，一共花费21体力；还可以先将12切成4+8，花费12体力，再将8切成3+5，花费8体力，一共花费20体力。显然，后者比前者更省体力。

那么，木匠至少要花费多少体力才能完成切割任务呢？

最后，我们来提供输入输出数据，由你来写一段程序，实现这个算法，只有写出了正确的程序，才能继续后面的课程。

输入

第1行：1个整数N(2 <= N <= 50000) 第2 - N + 1行：每行1个整数Li(1 <= Li <= 1000)。

输出

输出最小的体力消耗。

输入示例

3 3 4 5

输出示例

19

请选取你熟悉的语言，并在下面的代码框中完成你的程序，注意数据范围，最终结果会造成Int32溢出，这样会输出错误的答案。

不同语言如何处理输入输出，请查看下面的语言说明。

AC代码：

#include#includeusing namespace std;priority_queue< int ,vector, greater >q;int main(){ int n,i,j; int L,sum; long long ans; while(scanf("%d",&n)!=EOF){ while(!q.empty()) q.pop(); for(i=1;i<=n;i++){ scanf("%d",&L); q.push(L); } ans=0; while(q.size()!=1){ int a=q.top(); q.pop(); int b=q.top(); q.pop(); sum=a+b; ans+=sum; q.push(sum); } printf("%lld\n",ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。