哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出权值。
2
2 8
3
5 11 30
10 62 思路
哈夫曼编码可以快速解码，其原理是构成不平衡的二叉树
所有数都是叶节点
先进行排序；
取其中最小的两个构成一个二叉树，跟节点为这两个数的和；
然后把根节点放入再排序；
以此类推每选中两个数，总权重就加一次这两个数
得到以下代码
#include<iostream> #include<algorithm> using namespace std; int a[10005]; int main(){ int n; while(cin>>n){ for(int i=0;i<n;i++) cin>>a[i]; int sum=0; for(int i=n;i>=2;i--){ sort(a,a+i); sum+=a[0]+a[1]; a[0]=a[0]+a[1]; for(int j=1;j<n-1;j++) a[j]=a[j+1]; } cout<<sum<<endl; } return 0; }
原文：https://www.cnblogs.com/yfr2zaz/p/11029258.html