蓝桥杯训练-Huffman树(哈夫曼树)(day14)

一、题目

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,每个数不超过1000.

输出:

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

二、例子

输入:

5

5 3 8 2 9

输出:

59

三、涉及的知识

  • map()函数具体讲解:CSDN​​​​​​
  • append()函数具体讲解:CSDN
  • 列表删除元素语法:列表.pop(下标)

例:

mylist = ["rabbit","cat","dog"]
mylist.pop(2)
print(mylist)

运行结果:

['rabbit', 'cat'] 

  • 列表排序有两种方法:

1.list.sort():就地修改列表,返回None。

例:

mylist = [1,4,5,3,2]
mylist.sort()
print(mylist)

运行结果:

[1, 2, 3, 4, 5] 

2.sorted(列表):返回一个排序的新列表,原列表不变。

mylist = [1,4,5,3,2]
sorted(mylist)
print(mylist)

运行结果:

[1, 4, 5, 3, 2] 

四、python代码及逐行解析

n = int(input())
value = 0
list = list(map(int,input().split()))   #输入的值填入列表for i in range(n - 1):list = sorted(list)             #顺序排序value += list[0] + list[1]      #最小的两个数相加value_list = list[0] + list[1]  #被相加的两个数合并list.pop(0)                     #删除第一个数list.pop(0)                     #删除第二个数list.append(value_list)         #把合并后的数加到列表中
print(value)

运行结果:

4
1 8 3 10
38

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/254046.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【C#】.net core 6.0 设置根目录下某个文件夹可访问,访问创建的图片等资源

欢迎来到《小5讲堂》 大家好&#xff0c;我是全栈小5。 这是《C#》系列文章&#xff0c;每篇文章将以博主理解的角度展开讲解&#xff0c; 特别是针对知识点的概念进行叙说&#xff0c;大部分文章将会对这些概念进行实际例子验证&#xff0c;以此达到加深对知识点的理解和掌握。…

Fink CDC数据同步(六)数据入湖Hudi

数据入湖Hudi Apache Hudi(简称&#xff1a;Hudi)使得您能在hadoop兼容的存储之上存储大量数据&#xff0c;同时它还提供两种原语&#xff0c;使得除了经典的批处理之外&#xff0c;还可以在数据湖上进行流处理。这两种原语分别是&#xff1a; Update/Delete记录&#xff1a;H…

信创ARM架构QT应用开发环境搭建

Linux ARM架构QT应用开发环境搭建 前言交叉工具链Ubuntu上安装 32 位 ARM 交叉工具链Ubuntu上安装 64 位 ARM 交叉工具链 交叉编译 QT 库下载 QT 源码交叉编译 QT 源码 Qt Creator交叉编译配置配置 Qt Creator Kits创建一个测试项目 小结 前言 有没有碰到过这种情况&#xff1…

一文讲透Python函数中的形式参数和实际参数

函数参数包括形式参数和实际参数&#xff0c;简称形参和实参。其中形式参数即是在定义函数时函数后面括号中的参数列表&#xff08;parameterlist&#xff09;&#xff0c;比如上一个帖子的示例中的width, length&#xff1b;实际参数则是调用函数时函数后面括号中的参数值&…

Docker配置Portainer容器管理界面

目录 一、Portainer 简介 优点&#xff1a; 缺点&#xff1a; 二、环境配置 1. 拉取镜像 2. 创建启动容器 三、操作测试 1. 进入容器 2. 拉取镜像并部署 3. 访问测试 一、Portainer 简介 Portainer 是一个开源的轻量级容器管理界面&#xff0c;用于管理 Docker 容器…

开源免费的物联网网关 IoT Gateway

1. 概述 物联网网关&#xff0c;也被称为IOT网关&#xff0c;是一种至关重要的网络设备。在物联网系统中&#xff0c;它承担着连接和控制各种设备的重要任务&#xff0c;将这些设备有效地连接到云端、本地服务器或其他设备上。它既能够在广域范围内实现互联&#xff0c;也能在…

Docker部署前端项目

某次阿里云的自动流水线失败了&#xff0c;代码本地跑起来莫得问题&#xff0c;错误日志提示让我跑一下npm run build &#xff0c;但是俺忽然发现&#xff0c;我跑了&#xff0c;文件打包好了&#xff0c;但是往哪里运行呢&#xff1f;这涉及到要构建一个环境供打包文件部署吧…

RedissonClient妙用-分布式布隆过滤器

目录 布隆过滤器介绍 布隆过滤器的落地应用场景 高并发处理 多个过滤器平滑切换 分析总结 布隆过滤器介绍 布隆过滤器&#xff08;Bloom Filter&#xff09;是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是…

unity-ios-解决内购商品在Appstore上面已配置,但在手机测试时却无法显示的问题

自己这几天用 unity 2021 xcode 14.2 开发ios内购&#xff0c;appstore上面内购商品都已经配置好了&#xff0c;但是在手机里就是不显示&#xff0c;最后才发现必需得满足以下条件才行&#xff1a; 1. Appstore后台 -> 内购商品 -> 商品状态必需为『准备提交』以上状态…

Docker部署Grafana+Promethus监控Mysql和服务器

一、Grafana部署所需资源 Grafana 需要最少的系统资源&#xff1a; 建议的最小内存&#xff1a;512 MB建议的最低 CPU&#xff1a;1 官方文档&#xff1a;https://grafana.com/docs/grafana/latest/getting-started/build-first-dashboard/ 可以看到&#xff0c;我的这台服务…

放假--寒假自学版 day1(补2.5)

fread 函数&#xff1a; 今日练习 C语言面试题5道~ 1. static 有什么用途&#xff1f;&#xff08;请至少说明两种&#xff09; 1) 限制变量的作用域 2) 设置变量的存储域 2. 引用与指针有什么区别&#xff1f; 1) 引用必须被初始化&#xff0c;指针不必。 2) 引用初始…

Android中设置Toast.setGravity()了后没有效果

当设置 toast.setGravity()后&#xff0c;弹窗依旧从原来的位置弹出&#xff0c;不按设置方向弹出 类似以下代码&#xff1a; var toast Toast.makeText(this, R.string.ture_toast, Toast.LENGTH_SHORT)toast.setGravity(Gravity.TOP, 0, 0)//设置toast的弹出方向为屏幕顶部…

【Java八股面试系列】JVM-常见参数设置

目录 堆内存相关 显式指定堆内存–Xms和-Xmx 显式新生代内存(Young Generation) 显式指定永久代/元空间的大小 垃圾收集相关 垃圾回收器 GC 日志记录 处理 OOM JDK监控和故障处理工具总结 堆内存相关 Java 虚拟机所管理的内存中最大的一块&#xff0c;Java 堆是所有线…

汇编笔记 01

小蒟蒻的汇编自学笔记&#xff0c;如有错误&#xff0c;望不吝赐教 文章目录 笔记编辑器&#xff0c;启动&#xff01;debug功能CS & IPmovaddsub汇编语言寄存器的英文全称中英对照表muldivandor 笔记 编辑器&#xff0c;启动&#xff01; 进入 debug 模式 debug功能 …

Arm发布新的人工智能Cortex-M处理器

Arm发布了一款新的Cortex-M处理器&#xff0c;旨在为资源受限的物联网&#xff08;IoT&#xff09;设备提供先进的人工智能功能。这款新的Cortex-M52声称是最小的、面积和成本效率最高的处理器&#xff0c;采用了Arm Helium技术&#xff0c;使开发者能够在单一工具链上使用简化…

动漫风博客介绍页面源码

动漫风博客介绍页面源码&#xff0c;HTML源码&#xff0c;图片背景有淡入切换特效 蓝奏云&#xff1a;https://wfr.lanzout.com/iIDZu1nrmjve

Python调用matlab程序

matlab官网&#xff1a;https://ww2.mathworks.cn/?s_tidgn_logo matlab外部语言和库接口&#xff0c;包括 Python、Java、C、C、.NET 和 Web 服务。 matlab和python的版本 安装依赖配置 安装matlab的engine 找到matlab的安装目录&#xff1a;“xxx\ extern\engines\python…

【python量化交易】qteasy使用教程01 - 安装方法及初始化配置

qteasy教程1 - 安装方法及初始化配置 qteasy教程1 - 安装方法及初始配置qteasy安装前的准备工作1&#xff0c; 创建安装环境2&#xff0c;安装MySQL数据库 (可选)安装pymysql 3&#xff0c;创建tushare账号并获取API token (可选)4&#xff0c;安装TA-lib (可选)WindowsMac OSL…

Windows自动化实现:系统通知和任务栏图标自定义

文章目录 Windows自动化的三个小工具系统通知任务栏图标使用pystray实现使用infi.systray实现 Windows自动化的三个小工具 系统通知 import win10toastwin10toast.ToastNotifier().show_toast("eee", "休息一下", icon_path"icon.ico", durati…

uniapp中使用EelementPlus

uniapp的强大是非常震撼的&#xff0c;一套代码可以编写到十几个平台。这个可以在官网上进行查询uni-app官网。主要还是开发小型的软件系统&#xff0c;使用起来非常的方便、快捷、高效。 uniapp中有很多自带的UI&#xff0c;在创建项目的时候&#xff0c;就可以自由选择。而E…