3775 - 【START】2015暑期训练——Huffuman树
Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1}，用这列数构造Huffman树的过程如下：
- 找到{pi}中最小的两个数，设为pa和pb，将pa和pb从{pi}中删除掉，然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。
- 重复步骤1，直到{pi}中只剩下一个数。
在上面的操作过程中，把所有的费用相加，就得到了构造Huffman树的总费用。
本题任务：对于给定的一个数列，现在请你求出用该数列构造Huffman树的总费用。例如，对于数列{pi}={5, 3, 8, 2, 9}，Huffman树的构造过程如下：
- 找到{5, 3, 8, 2, 9}中最小的两个数，分别是2和3，从{pi}中删除它们并将和5加入，得到{5, 8, 9, 5}，费用为5。
- 找到{5, 8, 9, 5}中最小的两个数，分别是5和5，从{pi}中删除它们并将和10加入，得到{8, 9, 10}，费用为10。
- 找到{8, 9, 10}中最小的两个数，分别是8和9，从{pi}中删除它们并将和17加入，得到{10, 17}，费用为17。
- 找到{10, 17}中最小的两个数，分别是10和17，从{pi}中删除它们并将和27加入，得到{27}，费用为27。
- 现在，数列中只剩下一个数27，构造过程结束，总费用为5+10+17+27=59。
Input
输入第一行是一个整数M（M < 10），
第二行开始是M组输入
输入的第一行包含一个正整数n（n<=100），第二行是n个正整数，表示p0, p1, …, pn-1，每个数不超过1000。
Output
对应每组输入，输出为一个数即构造Huffman树的总费用，以换行符结束。
Examples
Input
2 2 42 256 5 5 3 8 2 9
Output
298 59
Solution C
#include <stdio.h> int huffman(int n,int p[100]); int main() { int m; scanf("%d",&m); int i,j; int n; int p[100]; int sum[10]; for(i=0;i<m;i++) { scanf("%d",&n); for(j=0;j<n;j++) { scanf("%d",&p[j]); } sum[i]=huffman(n,p); } for(i=0;i<m;i++) { printf("%d\n",sum[i]); } return 0; } int huffman(int n,int *p) { int a=0; int b=1; int i; int j=0; int sum=0; while(j<n-1) { for(i=0;i<n;i++) { if(p[a]>p[i]&&i!=b) { a=i; } } for(i=0;i<n;i++) { if(p[b]>p[i]&&i!=a) { b=i; } } p[a]=p[a]+p[b]; p[b]=1000000; sum+=p[a]; j++; } return sum; }
Solution C++
#include <stdio.h> int main() { //freopen("1.txt","r",stdin); //freopen("2.txt","w",stdout); int M; scanf("%d", &M); while(M--) { int i, j, k, l, n; int count = 0; scanf("%d", &n); int a[999]; for (i = 0; i < n; i++) scanf("%d", &a[i]); for (i = n; i > 1; i--) { k = 0, l = 1; if (a[0] < a[1]) k = 1, l = 0; for (j = 2; j < i; j++) { if (a[j] <= a[k]) { if (a[j] < a[l]) k = l, l = j; else k = j; } } a[l] += a[k]; count += a[l]; for (j = k; j < i - 1; j++) a[j] = a[j + 1]; } printf("%d\n", count); } return 0; }