7-8 修理牧场（25 分）（哈夫曼树）
发布时间
阅读量：
阅读量
农夫打算修复牧场某处围栏，在丈量后确定需要N块木材（每块木材长度为整数L_i个单位），因此他采购了一根足够长且可分割为N段的标准木材；其总长度等于各L_i之和
但是农夫自己没有使用锯子，请人代为锯木时所付费用与其所处理的那一段木材长度成正比关系。为了简化计算过程不妨假设该费用等于处理过的木材段落长度值例如对于一段长为20单位的木材要将其分割成长分别为8单位7单位以及5单位的三段应当首先进行如下操作：第一次切割将长条分为12单位与8单位两部分此时所需费用为20单位；第二次切割则仅需花费12单元即可将之前的12单元长条进一步分割为7单元与5单元两部分这样总共所需费用即为32单元相比而言如果采用另一种切割方案即先将木材分割为15单元与5单元两部分那么后续所需费用则会增加至15+15=30单元（大于32）
请编写程序帮助农夫计算将木头锯成N块的最少花费。
输入格式:
程序首先读取一个正整数 N（≤1e4）。接下来的一行包含 N 个不超过 50 的正整数（≤50），这些数字代表每一段木头的长度
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
思路：最初认为是贪心算法，并未意识到会采用哈夫曼编码技术。实际上应该得益于哈夫曼树的特性——其带权路径长度是最小的。在这里我们采用了优先队列来构建哈夫曼编码结构。
#include <bits/stdc++.h>
using namespace std;
int main()
{
priority_queue<int,vector<int>,greater<int> >l;
int n,a;
cin>>n;
for (int i=0; i<n; i++)
{
cin>>a;
l.push(a);
}
int sum=0;
while(l.size()!=1)
{
int x=l.top();
l.pop();
int y=l.top();
l.pop();
sum+=x+y;
l.push(x+y);
}
printf("%d\n",sum);
return 0;
}全部评论 (0)
还没有任何评论哟~