聪明的木匠之 霍夫曼树的实用(最小堆实现)

1117 聪明的木匠  题目来源： 河北大学算法艺术协会 基准时间限制：1 秒 空间限制：131072 KB 分值: 20  难度：3级算法题 一位老木匠需要将一根长的木棒切成N段。每段的长度分别为L1,L2,......,LN（1 <= 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体力。显然，后者比前者更省体力。 那么，木匠至少要花费多少体力才能完成切割任务呢？ Input 第1行：1个整数N(2 <= N <= 50000) 第2 - N + 1行：每行1个整数Li(1 <= Li <= 1000)。 Output 输出最小的体力消耗。 Input示例 3 3 4 5 Output示例 19

本题本质就是霍夫曼树！

霍夫曼树是一种带权路径长最短的二叉树，又叫做最优二叉树，常处理符号编写工作。

假设我们要给一个英文单字"F O R G E T"进行霍夫曼编码，每个英文字母出现的频率分别为2、3、4、4、5、7。

根据整组数据中符号出现的频率高低，决定如何给符号编码。如果符号出现的频率越高，则给符号的码越短，相反符号的号码越长。

1.构树

(1) 将w1、w2、…，wn看成是有n 棵树的森林(初始每棵树仅有一个结点); (2) 在森林中选出两个根结点的权值最小的树合并，且新树的根结点权值为其左、右子树根结点权值之和； (3) 从森林中删除(2)中选取的两棵树，并将新树加入森林； (4) 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

                     

2.编码

(1) 给霍夫曼树的所有左链接编码为'0'、右链接为'1'。

(2) 从树根至树叶依序记录所有字母的编码。    

对应此题，比如长度27的棍子，需要分割成2、5、7、13。则每次分割都要保证子树又是一个哈弗曼树。

结果为27+14+7 = 48。

//最小堆实现霍夫曼树 #include <iostream> #include <algorithm> #include <cstring> #include <queue> #define INF 0x3f3f3f3f #define NMAX 105 using namespace std; int n, x, ans, a[NMAX]; //1. 写成模板 template<class T> using min_heap = priority_queue<T, std::vector<T>, std::greater<T>>; min_heap<int> my_min_heap; //2. 自定义比较结构 struct cmp{ bool operator () (int &a, int &b){ //int类型 return a > b; //min_heap } }; priority_queue<int, vector<int>, cmp> pq; //3. greater原理同2 priority_queue<int,vector<int>, greater<int>> pq1; int main(){ while (cin>>n){ ans = 0; for (int i = 0; i < n; ++i) { cin>>x; pq.push(x); } //最小堆实现霍夫曼树 while (pq.size() > 1){ int a = pq.top();pq.pop(); int b = pq.top();pq.pop(); ans += a+b; pq.push(a+b); } cout<< ans <<endl; } return 0; }

    水过，通过做题复习知识也挺好，现在来看学过的东西感觉更清晰。讲真、