修理牧场

描述：

农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li 的总和。

但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。

为简单起见，不妨就设酬金等于所锯木头的长度。

例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。

如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。

请编写程序帮助农夫计算将木头锯成N块的最少花费。

问题分析：

由于一次锯木头产生花费的同时还产生2块木头，因此可以尝试用二叉树表示锯木头的过程，树的根节点是初始的木头，叶节点是最终需要的木块。

在树中非叶节点的权重等于其子节点的权重和，这样的树有很多种，每棵树所对应的锯木方法所产生的花费就是所有叶节点权重与其到根节点路径长度乘积的和
也就是求最小的带权路径长度(所有叶结点带权路径长度之和)，也就是哈夫曼树问题；我们可以逆向思考这个问题，即已经有N个锯开的木块，如何合并才能使合并的花费最少，可以使用哈夫曼算法；

给出一个我找到的很好的讲哈夫曼算法的博客，分享~

哈夫曼算法

哈夫曼树的构建可以通过优先队列的小根堆实现，每次合并所有节点里权值最小的两个，在哈夫曼树中就是每次合并根节点最小的两颗树，把新树加入合并的队伍中，把原来两棵树删除；

#include
using namespace std;
 
typedef unsigned long long ull;
typedef long long ll;
 
const ll maxx = 1e18;
const int N = 1e6+100;
const int p = 1e4;
const double eps = 1e-8;

priority_queue<int,vector<int>,greater<int> >pmin; 
int n,t,sum;

int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>t;
		pmin.push(t);
	}
	
	while(pmin.size()!=1)
	{
		int k1,k2;
		k1=pmin.top();
		pmin.pop();
		k2=pmin.top();
		pmin.pop();
		sum+=(k1+k2);
		
		pmin.push(k1+k2);
	}
	
	cout<<sum;
} 

反思：

之前的贪心题里做过一个合并果子的一个题，现在想想那个题也是求树的最小带权路径长度的问题，也要用哈夫曼算法来做。