756
九度题目1172：哈夫曼树
题目1172：哈夫曼树 时间限制：1 秒
内存限制：32 兆
特殊判题：否
提交：4366
解决：1827
题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题
目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37
来源：
2010年北京邮电大学计算机研究生机试真题
构建一颗哈弗曼树的方法：
1.根据给定的N{W1,W2,...,Wn}个权值构成N棵二叉树的集合F={T1,T2,...,Tn},其中每课二叉树Ti只有一个带权值为Wi的根节点，其左右子树为
空。
2.在F中选取两棵根节点最小的树作为左右子树构造一颗新的二叉树，且置新的二叉树的根节点的权值为其左右子树上根节点的权值之和。
3.在F中删除这两科树，同时将新得到的二叉树加入到F中。
4.重复2和3，直到F只含一棵树为止，这棵树便是哈弗曼树。
思路：所有的非叶子节点之和就是答案
AC代码：（没有构建树，仅仅模拟哈弗曼数组合节点）
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[1100];
int main()
{
int i,j,n,m,num,sum;
while(scanf("%d",&n)!=EOF)
{
memset(a,0,sizeof(a));
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
sort(a,a+n);
i=1;sum=0;
while(i<n)
{
sort(a+i-1,a+n);//每次都要重新排序,因为生成了新的节点
num=a[i]+a[i-1];//计算父亲
sum+=num;//非叶子节点之和
a[i]=a[i]+a[i-1];//将小树生成新的节点
i++;
}
printf("%d\n",sum);
}
return 0;
}
最后更新：2017-04-03 12:56:20