zwf88z

用户名：zwf88z

访问量：1309

签　名：

等　　级
排　　名	17325
经　　验	775
参赛次数	0
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-逆序排列-题解(Java代码)
浏览：198

蓝桥杯算法提高VIP-日期计算-题解(Java代码) 用JDK自带的日期函数，值得一看
浏览：316

你可能喜欢

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

蓝桥杯基础练习VIP-Huffuman树-题解(Java代码)

　　作者: zwf88z　　　　发表时间：2020-01-30 01:07:21 浏览：253　|　评论：0　

原题链接：蓝桥杯基础练习VIP-Huffuman树

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
	/*
	基础练习 Huffuman树 
	 
	问题描述
	　　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
	*/
	
	//计算总花费的费用
	static int sum = 0;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		//int num[] = new int[n];
		ArrayList<Integer> list = new ArrayList<>();
		for(int i=0;i<n;i++){
			list.add(sc.nextInt());
		}
		//排序
		ArrayList<Integer> a = f(list);
	    System.out.println(sum);
//		System.out.println(a);

}
	public static ArrayList a(ArrayList<Integer> list){
		//int j = list.get(0).intValue();
		//int k = list.get(1).intValue();
		int l = list.get(0) + list.get(1);
		sum += l;
		list.add(l);
		//System.out.println(list);
		//删除索引为0位置的元素之后继续删除新的索引为0位置
		list.remove(0);
		list.remove(0);
		//System.out.println(list);
		return list;
	}
	public static ArrayList f(ArrayList<Integer> a){
		//先排序
		for(int i=0;i<a.size();i++){
			Integer min = a.get(i);
			for(int j=i+1;j<a.size();j++){
				if(min > a.get(j)){
					Integer cur = min;
					min = a.get(j);
					a.set(i, min);
					a.set(j, cur);
				}
			}
		}
		//只要集合的长度不为1
		while(a.size()>1){
			//添加删除计算操作
			a = a(a);
			//递归继续
			f(a);
		}
		return a;
	}

}

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

zwf88z

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言考试练习题_保留字母（C语言代码）

开心的金明（C++代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

众数问题（C++代码）

蓝桥杯基础练习VIP-Huffuman树-题解(Java代码)

评论区

精彩推荐

C二级辅导-公约公倍（C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

钟神赛车（C++代码）

母牛的故事（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

【蟠桃记】（C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

The 3n + 1 problem （C语言代码）

zwf88z

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言考试练习题_保留字母 （C语言代码）

开心的金明 （C++代码）

C语言程序设计教程（第三版）课后习题6.10 （C语言代码）

众数问题 （C++代码）

蓝桥杯基础练习VIP-Huffuman树-题解(Java代码)

评论区

精彩推荐

C二级辅导-公约公倍 （C语言代码）

C语言程序设计教程（第三版）课后习题9.2 （C语言代码）

钟神赛车 （C++代码）

母牛的故事 （C语言代码）

输出正反三角形 （C语言代码）格式错误！！！

C语言程序设计教程（第三版）课后习题8.1 （C语言代码）

【蟠桃记】 （C语言代码）

C语言程序设计教程（第三版）课后习题6.8 （C语言代码）

C语言程序设计教程（第三版）课后习题8.5 （C语言代码）

The 3n + 1 problem （C语言代码）

C语言考试练习题_保留字母（C语言代码）

开心的金明（C++代码）

众数问题（C++代码）

　　评论区

C二级辅导-公约公倍（C语言代码）

钟神赛车（C++代码）

母牛的故事（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

【蟠桃记】（C语言代码）