洛谷-UVA12676 Inverting Huffman(反转树)

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

来源：[https://www.luogu.com.cn/problem/UVA12676][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  算法生成的不同字符 的编码长度。

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

**输出：**

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

举例：

输入：

3 1 2 3

输出：  
5

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70][]

#include <bits/stdc++.h>
    using namespace std;
    vector<int> deep[100]; //已知条件是知道编码长度，则就是知道了该节点的深度，同一深度可能有多次合并。 
    int main(){
    	int n;
    	cin>>n;
    	int maxDeep=0; 
    	for(int i=0;i<n;i++){
    		int m;
    		cin>>m; //编码长度 等于 节点深度 
    		deep[m].push_back(0);//用0占位 
    		
    		//跟新并记录最大层数 
    		if(m>maxDeep){
    			maxDeep=m;
    		} 
    	}
    	
    	//假设叶子节点的权重(初值为1，因为最深层权重最小为1)
    	int temp=1;
    	
    	//深度为m,则需要m-1次合并，自下而上 
    	for(int i=maxDeep;i>0;i--){
    		for(int j=0;j<deep[i].size();j++){
    			if(deep[i][j]==0){//如果等于0 就代表是叶子节点 
    				deep[i][j]=temp;//将叶子节点假设为上一层节点的最大权重 
    			}					
    		}
    		sort(deep[i].begin(),deep[i].end());//第i层从小到大排序，原因：获得该层节点的最大的权值 
    		//合并
    		for(int j=0;j<deep[i].size();j=j+2){
    			deep[i-1].push_back(deep[i][j]+deep[i][j+1]);//新生成的双亲节点(反向生成中间节点) 
    			temp=deep[i][deep[i].size()-1];//保存该层节点的最大权值 
    		}
    	}
    	cout<<*deep[0].begin()<<endl;
    	return 0;
    }

**注意：权值可能很大，数组可定义为long long类型**

[https_www.luogu.com.cn_problem_UVA12676]: https://www.luogu.com.cn/problem/UVA12676
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191209210749495.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODc3MTg0,size_16,color_FFFFFF,t_70