“Don’t bark up the wrong Binary Tree.”
【问题描述】
我们称树的带权路径长度（WPL）最小的二叉树为“哈夫曼树”或“最优二叉树”。
哈夫曼树对字符进行编码，称为哈夫曼树编码(Huffman Coding)。哈夫曼编码是一种编码方式，哈夫曼编码是可变字长编码的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。
现在给定 n 个字符在文章中出现的频率：W[1], W[2],…, W[n]，给每个字符赋予一个01串，使得任意一个字符的编码不是另一个字符编码的前缀（哈夫曼编码），而且编码的总长度（每个字符的频率于编码长度的乘积总和）尽量小。
【输入格式】
第一行是一个整数n，表示n个字符的出现频率。 以下n行，每行有三一个整数W[i]。
【输出格式】
一个整数，表示n个字符的编码总长度。
【输入样例】
6 45 13 12 16 9 5
【输出样例】
224
【数据范围】
n<=40000，w[i]<=50000
一些小分析~
about题目样例： 不正经的公式证明（大概是这个意思就好了(￣▽￣)／）：
#include<algorithm>
#include<iostream>
#include<fstream>
#include<cstdio>
#include<queue>
using namespace std;
priority_queue<int,vector<int>, greater<int> > q;
int main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int t;
scanf("%d",&t);
q.push(t);
}
long long sum=0;
while(!q.empty()){
int not_leaf=0;
if(q.size()>=2){
//取两次最小值合成非叶节点
not_leaf+=q.top();
q.pop();
not_leaf+=q.top();
q.pop();
sum+=not_leaf;//sum(W[i]·P[l]=非叶节点权值和)
q.push(not_leaf);
}
else break;
}
printf("%lld",sum);
return 0;
}
[转载请标明出处 , 谢谢]
