【PTA】7-29 修理牧场 (哈夫曼树)
7-29 修理牧场 (25 分)
农夫需要修复牧场一段栅栏。
他测量后发现需要购买N块木材，并且每一块木材的长度都是整数值Li（单位：长度单位）。
因此他购买了一根足够长且可切割成N段的木材。
但是农夫自己并没有准备好所需的工具，请人代劳进行木材切割时所获得的报酬与其被切割下来的这段木材长度之间存在直接关系。为了便于说明问题，在不改变基本原理的前提下我们可以假设将每段木材的长度作为支付报酬的标准来使用。例如，在处理一根长20米的木材时希望将其分割成长度分别为8米、7米和5米的三段木材：首先进行切割所需费用共计20元人民币（或其他货币单位），此时木材被分成了12米和8米两部分；随后再次切割较长部分所需费用则增加至12元人民币（或其他货币单位），最终总共耗费了32元人民币（或其他货币单位）。如果我们在第一次切割时选择了不同的方式即把木材分割成长15米和5米两段则下一次切割所需费用将是15元人民币（或其他货币单位），最终总计则上升至35元人民币（或其他货币单位），这显然高于之前的策略所得。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
程序首先接收一个不超过104的正整数值N，并将其作为分割目标木头为N段的指令。随后读入的一行包含N个不超过50的整数值，这些数值即代表了每一段木块的具体长度信息。
输出格式:
输出一个整数，即将木头锯成N块的最少花费。
输入样例:
8
4 5 1 2 1 3 1 1
输出样例:
49
根据题意可以看出是树的数据结构，根结点是最初木块的长度，最后的木头是叶子结点，题目要求的是根据n个叶子结点构造一棵树并使结点权重总和-叶子结点的权重和最小，其实就和哈夫曼树的定义差不多。
哈夫曼树定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的wpl达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。
wpl是各个叶子结点权重乘以路径的长度总和，刚好等于非叶子结点的权重和。因此此题就是构造哈夫曼树。
下面用优先队列构造哈夫曼树。
#include <iostream>
#include <queue>
using namespace std;
int main()
{
priority_queue< int, vector<int>, greater<int> > Q;
int N, x, a, b, ans = 0;
cin>>N;
for(int i = 0;i < N;i++)
{
cin>>x;
Q.push(x);
}
for(int i = 0;i < N-1;i++)
{
a = Q.top();
Q.pop();
b = Q.top();
Q.pop();
Q.push(a+b);
ans += a+b;
}
cout<<ans<<endl;
return 0;
}