在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
基础练习 Huffuman树
时间限制:1.0s 内存限制:512.0MB
问题描述
Huffman树在编码中有着广泛的应用。在这里,我们只关心Huffman树的构造过程。
给出一列数{pi}={p0, p1, …, pn-1},用这列数构造Huffman树的过程如下: 1. 找到{pi}中最小的两个数,设为pa和pb,将pa和pb从{pi}中删除掉,然后将它们的和加入到{pi}中。这个过程的费用记为pa + pb。 2. 重复步骤1,直到{pi}中只剩下一个数。 在上面的操作过程中,把所有的费用相加,就得到了构造Huffman树的总费用。 本题任务:对于给定的一个数列,现在请你求出用该数列构造Huffman树的总费用。 例如,对于数列{pi}={5, 3, 8, 2, 9},Huffman树的构造过程如下: 1. 找到{5, 3, 8, 2, 9}中最小的两个数,分别是2和3,从{pi}中删除它们并将和5加入,得到{5, 8, 9, 5},费用为5。 2. 找到{5, 8, 9, 5}中最小的两个数,分别是5和5,从{pi}中删除它们并将和10加入,得到{8, 9, 10},费用为10。 3. 找到{8, 9, 10}中最小的两个数,分别是8和9,从{pi}中删除它们并将和17加入,得到{10, 17},费用为17。 4. 找到{10, 17}中最小的两个数,分别是10和17,从{pi}中删除它们并将和27加入,得到{27},费用为27。 5. 现在,数列中只剩下一个数27,构造过程结束,总费用为5+10+17+27=59。 输入格式
输入的第一行包含一个正整数n(n<=100)。
接下来是n个正整数,表示p0, p1, …, pn-1,每个数不超过1000。 输出格式
输出用这些数构造Huffman树的总费用。
样例输入
5
5 3 8 2 9 样例输出
59
作者注释:先排序后操作。
1 #include<stdio.h> 2 int main(){ 3 int n; 4 int all=0,flag=0; 5 scanf("%d",&n); 6 int a[n]; 7 //录入数组 8 for(int i=0;i<n;i++){ 9 scanf("%d",&a[i]); 10 } 11 for(int p=0;p<n-1;p++){//控制循环次数 12 //选择排序升序 13 for(int i=0;i<n-1;i++){ 14 for(int j=i+1;j<n;j++){ 15 if(a[i]>a[j]){ 16 int t = a[i]; 17 a[i] = a[j]; 18 a[j] = t; 19 } 20 } 21 } 22 all+=a[flag]+a[flag+1];//all为最小两位之和 23 a[flag+1]+=a[flag];//第二小位置上存放最小两数之和 24 a[flag]=0;//最小位清0 25 flag++; 26 } 27 printf("%d",all); 28 return 0; 29 }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论