哈夫曼树、优先队列

今日腊月二十八，上午写了对联，下午敲代码，晚上玩手机…
还得再自控力强一些呀
下午主要精力用来写PTA上的一道题：修理牧场。题目如下：
7-29 修理牧场 (25分)
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数L​i​​个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是L​i​​的总和。
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
先考虑用哈夫曼树来解决，，，不过这个知识忘得差不多了，，还要建树，有亿点麻烦。

哈夫曼树

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。（百度百科）
哈夫曼树在编码中的应用是根据编码出现的频率来给予不同的长度，从而节约空间。

算法（建树）原理

根据给定的数据（数组），选取两个数组中最下的树形成一棵子树，其双亲的权值设置为两个结点的权值之和，再将其父母加入数组，再次选取无父母的数组中最小的两个结点形成子树，，，以此类推。由于哈夫曼树是二叉树，且其只有零度结点与二度结点，故有：n₀=n₂+1；易知，结点总数为2*n-1；

故可以考虑用一个结构体数组来存储各个结点的信息。以修理牧场该题为例，假设需要得到的木头数为N，可开辟一个大小为2*N的数组，将新生成的父母结点加入到N+ 1、N+2、…
树的结构如下：

struct Node{int data;int parent;int lchild;int rchild;
};

与一般的树形结构类似，并无特别之处。
从数组中选取两个“最小”的数：

void find(Node* Btree,int m,int &s1,int &s2){int minn1=55,minn2=55;s1=s2=0;for(int i=1;i<m;i++){if(Btree[i].data<minn1&&Btree[i].parent==-1){minn1=Btree[i].data;s2=i;}}for(int i=1;i<m;i++){if(Btree[i].data<minn2&&Btree[i].parent==-1){if(i!=s2){s1=i;minn2=Btree[i].data;}}} 
}

建树：

Node* Create(Node* Btree){Btree=new Node[2*N];for(int i=1;i<=N;i++){scanf("%d",&Btree[i].data);Btree[i].lchild=Btree[i].parent=Btree[i].rchild=-1;}for(int i=N+1;i<2*N;i++){int s1,s2;find(Btree,i,s1,s2);Btree[i].parent=-1;Btree[i].data=Btree[s1].data+Btree[s2].data;Btree[s1].parent=Btree[s2].parent=i;Btree[i].lchild=s1,Btree[i].rchild=s2;}
return Btree;
}

遗憾的是，，，这个方法只通过了一个测试点，，迷惑。。

优先队列

还是偷瞄了一眼别人的代码，才拍拍脑袋想起这么个好用极了的东东。
实现方法：
建立一个只包含一个数据成员的结构体，并重载<号。这里对为何重载<号不是很明了。答：优先队列默认从大到小排列，若想要使数小的结点先出队，便要重载小于号！

struct Node{int data;friend bool operator <(Node a,Node b){return a.data>b.data;//数组的排序。。。如果a>b，则无需交换顺序}
};

之后建立一个优先队列，数据类型为结构体。一次插入数据，优先队列会自动排序，使小的在前面，大的数据在后面，之后每次拿出队列前两个数据，生成的双亲结点再次入队即可。
全代码：

#include
#include
#include
#include
#include
#include
#define ll long long
#define INF 10000
#include
#include
#include
#include
#include
using namespace std;
struct Node{int data;friend bool operator <(Node a,Node b){return a.data>b.data;//数组的排序。。。如果a>b，则无需交换顺序}   
};
priority_queue<Node>Q;
int main(){int N;scanf("%d",&N);for(int i=0;i<N;i++){int a;scanf("%d",&a);Node n;n.data=a;Q.push(n);}int ans=0;while(!Q.empty()){int a=Q.top().data;Q.pop();if(Q.empty()) break;int b=Q.top().data;Q.pop();ans+=a+b;Node n;n.data=a+b;Q.push(n);}cout<<ans<<endl;return 0;
}

这次就AC了。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！