Huffman树
时间： 1ms 内存：128M
描述：
我们大家都学习了Huffman算法，给出每一个点的权值，它可以求出一个具有最小加权外部路径的二叉树，也就是使造价 W(k1)*Lk1 + ... + W(kn)*Lkn (树枝长度为根结点到叶结点边数)最小的二叉树。现在由你来完成这项工作。
输入：
输入一共有2行。
第一行为一个整数n，它表示点的个数。
第二行有n(1 < n <= 1000)个数，第i（1 <= i <= n）个数表示第i个点的权值
输出：
输出为一个数，为最小造价值。
示例输入：
5
10 5 20 10 18
示例输出：
141
提示：
参考答案（内存最优[752]）：
#include<stdio.h>
typedef struct node {
int weight;
int ok;
}NODE;
int main()
{
int n,n1,n2,i,j,min1,min2,sum=0;
NODE t[2002];
scanf("%d",&n);
for(i = 0;i < n;i++)
{
scanf("%d",&t[i].weight);
t[i].ok = 1;
}
for(i = n;i < 2*n-1;i++)
{
n1 = n2 = -1;
min1 = min2 = 999999;
for(j = 0;j < i;j++)
{
if (t[j].ok)
{
if (t[j].weight < min1)
{
min2 = min1;
n2 = n1;
min1 = t[j].weight;
n1 = j;
}
else if (t[j].weight < min2)
{
min2 = t[j].weight;
n2 = j;
}
}
}
t[i].weight = t[n1].weight + t[n2].weight;
sum += t[i].weight;
t[i].ok = 1;
t[n1].ok = t[n2].ok = 0;
}
printf("%d",sum);
return 0;
}
参考答案（时间最优[0]）：
#include<stdio.h>
typedef struct node {
int weight;
int ok;
}NODE;
int main()
{
int n,n1,n2,i,j,min1,min2,sum=0;
NODE t[2002];
scanf("%d",&n);
for(i = 0;i < n;i++)
{
scanf("%d",&t[i].weight);
t[i].ok = 1;
}
for(i = n;i < 2*n-1;i++)
{
n1 = n2 = -1;
min1 = min2 = 999999;
for(j = 0;j < i;j++)
{
if (t[j].ok)
{
if (t[j].weight < min1)
{
min2 = min1;
n2 = n1;
min1 = t[j].weight;
n1 = j;
}
else if (t[j].weight < min2)
{
min2 = t[j].weight;
n2 = j;
}
}
}
t[i].weight = t[n1].weight + t[n2].weight;
sum += t[i].weight;
t[i].ok = 1;
t[n1].ok = t[n2].ok = 0;
}
printf("%d",sum);
return 0;
}
题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。