洛谷-UVA12676 Inverting Huffman(反转树)

小咪咪 2023-06-20 09:21 64阅读 0赞

来源:https://www.luogu.com.cn/problem/UVA12676

题目大意:已知huffman编码长度,反过来估计各叶子结点的最小权重和。

这里面的隐含条件就是:
1)求各叶子节点的权重和 = 求huffman树根节点的权重
2)**
(重点)**上层叶子节点一定至少是下层各节点权重的最大值!(这也解决了如何让叶子节点的权重和最小问题)

最重要的解题思路是:

从上而下推理,假设最深层权重假设全为1(保证得到最小权重),下层节点合并,得到上层新生成的中间节点,而原有的上层的叶子节点等于**是下层各节点权重的最大值,再继续合并,直到合并为最终的根节点。**

输入:

输入文件包含多个测试用例,每个测试用例如下所述:

第一行包含一个整数 N ( 2≤N≤50 ),表示文本中出现的不同字符数。

第二行包含 N 个整数 Li ( 1≤Li≤50 , i=1,2, … ,N ) , 表示由 huffman 算法生成的不同字符 的编码长度。

假设至少存在一棵上述算法构建的树,可以生成具有给定长度的编码。

输出:

对每个测试用例,输出一行,表示所有字符总数的最小值。

举例:

输入:

4

3 1 2 3

输出:
5

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<int> deep[100]; //已知条件是知道编码长度,则就是知道了该节点的深度,同一深度可能有多次合并。
  4. int main(){
  5. int n;
  6. cin>>n;
  7. int maxDeep=0;
  8. for(int i=0;i<n;i++){
  9. int m;
  10. cin>>m; //编码长度 等于 节点深度
  11. deep[m].push_back(0);//用0占位
  12. //跟新并记录最大层数
  13. if(m>maxDeep){
  14. maxDeep=m;
  15. }
  16. }
  17. //假设叶子节点的权重(初值为1,因为最深层权重最小为1)
  18. int temp=1;
  19. //深度为m,则需要m-1次合并,自下而上
  20. for(int i=maxDeep;i>0;i--){
  21. for(int j=0;j<deep[i].size();j++){
  22. if(deep[i][j]==0){//如果等于0 就代表是叶子节点
  23. deep[i][j]=temp;//将叶子节点假设为上一层节点的最大权重
  24. }
  25. }
  26. sort(deep[i].begin(),deep[i].end());//第i层从小到大排序,原因:获得该层节点的最大的权值
  27. //合并
  28. for(int j=0;j<deep[i].size();j=j+2){
  29. deep[i-1].push_back(deep[i][j]+deep[i][j+1]);//新生成的双亲节点(反向生成中间节点)
  30. temp=deep[i][deep[i].size()-1];//保存该层节点的最大权值
  31. }
  32. }
  33. cout<<*deep[0].begin()<<endl;
  34. return 0;
  35. }

注意:权值可能很大,数组可定义为long long类型

发表评论

表情:
评论列表 (有 0 条评论,64人围观)

还没有评论,来说两句吧...

相关阅读