蓝桥杯VIP试题 之 基础练习 Huffuman树 - JAVA

基础练习 Huffuman树 - JAVA解题

问题描述
　　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

import java.util.Scanner;

public class Main { public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner (System.in); //接收输入的数组长度和数组值 int a=sc.nextInt(); int[] array = new int[a]; for(int i=0;i<array.length;i++){ array[i] = sc.nextInt(); } /*校验存的输入的数组对不对 for(int i=0;i<array.length;i++){ System.out.println(array[i]); } */ //主要逻辑:找出数组中两个最小的数求和,并将和放进去 --> 依次循环,直至剩一个数 int[] arraySum = new int[a*2];
		int minNum1 = 0,minNum2 = 0; //每次循环取一个数,两次记为一次求和,即循环次数 = (数组长度-1) *2
		for(int i=0;i<(a-1)*2;i++)	{ //找到最小数的索引 int index = -1; //第一次找到最小值 if(i%2 == 0){ minNum1 = 99999; for(int j=0;j<array.length;j++){ //找一个不等于-1的最小值 if((array[j] != -1) &&(minNum1 > array[j])){ minNum1 = array[j]; index = j; } } //若没找到则表示数组中已经全部找完了 if(index != -1){ //若找到 -- 将找到的数在数组中的索引赋值为-1 array[index] = -1; }else{ minNum1 = 0; } }else{ minNum2 = 99999; //同样的方法找第二个 for(int j=0;j<array.length;j++){ if((array[j] != -1) &&(minNum2 > array[j])){ minNum2 = array[j]; index = j; } } //找到了最小的数,存下和,并赋值 if(index != -1){ array[index] = minNum1 + minNum2; arraySum[i]  = minNum1 + minNum2; }else{ minNum2 = 0; } }
		} /* //此时数组中的数应该都是-1
		for(int j=0;j<array.length;j++){ System.out.println(array[j]); } */ //求和 int sum = 0; for(int j=0;j<arraySum.length;j++){ //System.out.println(arraySum[j]); sum += arraySum[j]; } System.out.println(sum);
	}	
}


  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/104552691