蓝桥杯 Huffman树

女爷i 2024-03-27 15:55 98阅读 0赞

问题描述

Huffman树在编码中有着广泛的应用。在这里，我们只关心Huffman树的构造过程。  
　　给出一列数\{ *pi*\}=\{ *p*0, *p*1, …, *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*个正整数，表示*p*0, *p*1, …, *pn*\-1，每个数不超过1000。

输出格式

输出用这些数构造Huffman树的总费用。

样例输入

5  
5 3 8 2 9

样例输出

代码实现：

import java.util.Scanner;
    import java.util.Arrays;
    public class Main {  
        public static void main(String args[]){  
            Scanner in=new Scanner(System.in);
            int n=in.nextInt();
            int a[]=new int[n];
            for(int i=0;i<n;i++) {//输入数据
            	a[i]=in.nextInt();
            }
            int money=0;//总费用
            int max=0;//占位符
            int count=0;//当前循环次数
            int temp=a.length-1;//总循环次数
            for(int i=0;i<n;i++) {
            	max+=a[i];//保证占位符比数组中其它数大，不影响排序
            }
            while(a.length!=count+1) {//循环n-1次后，得出总费用；
            	Arrays.sort(a);//从小到大排序，占位符要大于数组中的其它数不影响排序
            	money=a[0]+a[1]+money;
            	a[0]=a[0]+a[1];
            	for(int i=1;i<temp;i++) {
            		a[i]=a[i+1];//向后移一位；
            	}
            	a[a.length-count-1]=max;//空出的位置用占位符占位；
            	count++;
            }//while
            System.out.println(money);
        }  
    }

Arrarys.sort()是用于给数组排序的，默认的情况下，是顺序排序，即从小到大。

感觉有用的话点个小赞吧！