蓝桥备赛——堆队列

 

AC code 

import os
import sys
import heapq
a = []
b = []
n,k = map(int,input().split())for _ in range(n):x,y = map(int,input().split())a.append(x)b.append(y)
q = []# 第一种情况:不打第n个怪兽# 将前n-1个第一次所需能量加入堆
for i in range(n-1):heapq.heappush(q,(a[i],i))t = k
ans = 0
while t > 0:
# 每次从堆中弹出最小的一个w,i = heapq.heappop(q)
#然后弹入第二次以后击打所需能量heapq.heappush(q,(b[i],i))
#答案加上该能量ans += w
#次数减一t -= 1# 第二种情况:考虑打第n个怪兽
ans2 = 0
#因为前n-1个一定要打,所以要打到n就必须保证击打次数大于等于n
if k >= n:
#因为前n-1个一定要打,所以先把所有第一次击打所需能量加和,
#然后再加上所有第二次以后击打所需能量的最小值*剩余击打次数ans2 += sum(a) + (k-n) * min(b)# 取最小值
if k >= n:print(min(ans,ans2))
else:print(ans)

感觉这道题除了使用了heapq(堆排列)之外,没有使用其他的数据结构知识。 

背景知识

在介绍堆排列之外,先补充一些有关大根堆、小根堆的知识

大根堆

每个结点的值都大于其左孩子和右孩子结点的值,称之为大根堆。

小根堆

每个结点的值都小于其左孩子和右孩子结点的值,称之为小根堆。

结合上述图片可直观看出来。

 我们将上面图片按照标号进行映射,可以获得对应的数组如下图所示(注意,此方法是一个重要的过程,涉及到如何将图转化为程序代码,也是我原来一直困惑的地方)

如上图,成功将树的形式转换成了数组(列表)形式了。

堆的特点就是FIFO(first in first out)先进先出。
堆在接收数据的时候先接收的数据会被先弹出。
栈的特性正好与堆相反,是属于FILO(first in/last out)先进后出的类型。

 heapq库常见函数及用法

简单了解了大小根堆后,对于heapq库大家应该有更好的理解了。

首先,介绍一下heapq的用法。

heapq属于Python的一个内置库,里面

heappush函数

import heapq
item=[1,56,7,54,33]
heapq.heappush(item,10)
print(item)[1, 56, 7, 54, 33, 10]Process finished with exit code 0

上述代码可知,heappush函数对应就是尾插法插入堆中新元素。

heappop函数

import heapq
item=[1,56,7,54,33]
heapq.heappop(item)
print(item)[7, 56, 33, 54]Process finished with exit code 0

将heap的最小值pop出heap,heap为空时报IndexError错误.

此处有一个注意事项,将最小值pop出堆后,会出现原item顺序改变的情况,why?

`heapq.heappop()` 函数在 Python 中会从堆中移除并返回最小的元素。然而,它不保证保持原始顺序。你观察到顺序变化的原因是因为 `heapq` 模块维护堆属性,即最小的元素始终位于根部,但不保证剩余元素的顺序。

当你执行 `heapq.heappop(item)` 时,最小的元素(在这里是 `1`)从堆(`item` 列表)中移除,并且堆属性被恢复。这个操作可能涉及重新排序列表中的元素以保持堆结构,从而导致与原始列表不同的顺序。

如果你想在移除元素时保持原始顺序,你应该使用其他方法,比如在使用堆操作之前对列表进行排序,或者维护一个单独的列表来保存原始顺序。

heappushpop(heap,item)

不再过多解释,两个参数,一个进一个出

pop出heap中最小的元素,推入item。

import heapq
item=[1,56,7,54,33]
heapq.heappushpop(item,12)
print(item)[7, 56, 12, 54, 33]Process finished with exit code 0

以上就是常见的heapq库中函数相关用法。

本题思路

首先考虑在不击败最后一个boss的情况下:

        每种怪兽只打一次,对应所需要的能量值为多少。最后再求出对应继续打怪兽,(消灭第二次),直到对应龙之泪达到所需要求。

        第二类情况,考虑消灭最后一只龙的情况,这时需要特判,考虑打最后一只怪兽的条件,对应要求n-1只怪兽要全部消灭至少一次。即总打击次数>=n,然后再加上所有第二次以后击打所需能量的最小值*击打次数。

        最终将两类情况对应的能量消耗取最小值即为最终结果。

不知各位道友看完此篇博客之后,有没有变得念头通达了呢?【手动狗头】

        

参考链接:

堆排序及python中heapq堆详解_heapq 用法 实现大根堆-CSDN博客

Python内置的heapq模块简析_python heappush 指定排序-CSDN博客 

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

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

相关文章

【edge浏览器无法登录某些网站,以及迅雷插件无法生效的解决办法】

edge浏览器无法登录某些网站,以及迅雷插件无法生效的解决办法 edge浏览器无法登录某些网站,但chrome浏览器可以登录浏览器插件无法使用,比如迅雷如果重装插件重装浏览器重装迅雷后仍然出现问题 edge浏览器无法登录某些网站,但chro…

网站业务对接DDoS高防

准备需要接入的网站域名清单,包含网站的源站服务器IP(仅支持公网IP的防护)、端口信息等。所接入的网站域名必须已完成ICP备案。如果您的网站支持HTTPS协议访问,您需要准备相应的证书和私钥信息,一般包含格式为.crt的公…

linux 组建raid5详细操作

raid5最多运行损坏一个盘,最少3个盘,容量为少一块硬盘的容量之和。 如果硬盘数量较多,比如8块以上,建议用raid6,raid6最多允许两块硬盘损坏。 如果需要 一、安装raid软件 deb包 apt-get install mdadm或dnf包 dnf …

Servlet基础 管理员注册页面

管理员注册页面 index.jsp <% page language"java" import"java.util.*" pageEncoding"UTF-8"%> <% String path request.getContextPath(); String basePath request.getScheme()"://"request.getServerName()":&quo…

小程序UI设计规范,界面设计尺寸详解

作为互联网技术的重要组成部分&#xff0c;小程序在日常生活中发挥着越来越重要的作用。因此&#xff0c;了解和严格遵守小程序的 UI 设计标准非常重要&#xff0c;它不仅可以帮助我们在保证良好用户体验的同时优化小程序&#xff0c;还可以使我们的产品在竞争激烈的市场中占据…

智慧乡村建设新篇章:数字乡村引领农村发展新时代

目录 一、智慧乡村的内涵与建设的必要性 二、智慧乡村建设的路径探索 &#xff08;一&#xff09;加强信息基础设施建设&#xff0c;夯实智慧乡村发展基础 &#xff08;二&#xff09;推动农业智能化升级&#xff0c;提升农业生产效率和质量 &#xff08;三&#xff09;推…

接口自动化框架搭建(四):pytest的使用

1&#xff0c;使用说明 网上资料比较多&#xff0c;我这边就简单写下 1&#xff0c;目录结构 2&#xff0c;test_1.py创建两条测试用例 def test_1():print(test1)def test_2():print(test2)3&#xff0c;在pycharm中执行 4&#xff0c;执行结果&#xff1a; 2&#xff0…

Windows11系统缺少相关DLL解决办法

一.缺少msvcp120.dll 下载Mircrosoft Visual C 2015等系统关键组件 Microsoft Visual C 2015-2022 Redistributable (x86) - 14.34.31931 Installation Error etc.. - Microsoft Q&A 二.缺少python27.dll 重新下载python2.7进行安装(选择Windows x86-64 MSI installer)…

Vidmore Video Fix for Mac 视频修复工具

Vidmore Video Fix for Mac是一款功能强大且易于使用的视频修复工具&#xff0c;专为Mac用户设计。它凭借先进的视频修复技术&#xff0c;能够帮助用户解决各种视频问题&#xff0c;如视频文件损坏、无法播放、格式不支持等。 软件下载&#xff1a;Vidmore Video Fix for Mac v…

matlab及其在数字信号处理中的应用001:软件下载及安装

目录 一&#xff0c;matlab的概述 matlab是什么 matlab适用于的问题 matlab的易扩展性 二&#xff0c;matlab的安装 1&#xff0c;解压所有压缩文件 2&#xff0c;解压镜像压缩文件 3&#xff0c;运行setup.exe 4&#xff0c;开始安装 5&#xff0c;不要运行软件…

谷粒商城实战(007 压力测试)

Java项目《谷粒商城》架构师级Java项目实战&#xff0c;对标阿里P6-P7&#xff0c;全网最强 总时长 104:45:00 共408P 此文章包含第141p-第p150的内容 简介 安装jmeter 安装jmeter 使用中文 这样写就是200个线程循环100次 一共是2万个请求 介绍线程组 添加请求 可以是htt…

绿联 安装Uptime Kuma - 一款开源的服务器监控和状态检测工具

Uptime Kuma 功能简介 Uptime Kuma 是一款开源的服务器监控和状态检测工具&#xff0c;它帮助您跟踪服务器的可用性、性能和健康状态。 主要功能&#xff1a; 服务器监控 Uptime Kuma 可以监控多个服务器&#xff0c;包括 Web 服务器、数据库服务器、应用程序服务器等。 它会定…

【Java】Integer 什么是128陷阱(源码分析)

一、128陷阱演示 public static void main(String[] args) {Integer a 110;Integer b 110;Integer c 130;Integer d 130;System.out.println(ab);System.out.println(cd);} 在上面的方法中我定义了四个变量a、b、c和d并且进行了两次比较。你认为输出结果是什么&#xff1f;…

超卖问题的 4 种解决方案来了,太硬核了

大家好&#xff0c;我是路人&#xff0c;最近刚推出的《Java 高并发 & 微服务 & 性能调优实战案例 100 讲》&#xff0c;此课程目前已发布上线&#xff0c;正在连载中&#xff0c;文末有观看方法。 所有案例均源于个人工作实战&#xff0c;均提供原理讲解 & 亲手敲…

物联网监控可视化是什么?部署物联网监控可视化大屏有什么作用?

随着物联网技术的深入应用&#xff0c;物联网监控可视化成为了企业数字化转型的关键环节。物联网监控可视化大屏作为物联网监控平台的重要组成部分&#xff0c;能够实时展示物联网设备的运行状态和数据&#xff0c;为企业管理决策和运维监控提供了有力的支持。今天&#xff0c;…

UE5学习日记——蓝图节点前缀关键字整理

一、起因 节点如海&#xff0c;中英文翻译的时候还是有差别的&#xff0c;比如&#xff1a; 同一个中文&#xff0c;可能在英文里完全不同&#xff0c;连出现位置可能都不一样 附加 Attach Actor To Component&#xff08;将Actor附加到组件&#xff09;Append Array&#xf…

DevSecOps平台架构系列-微软云Azure DevSecOps平台架构

目录 一、概述 二、Azure DevOps和黄金管道 2.1 概述 2.2 Azure DevOps架构说明 2.2.1 架构及管道流程图 2.2.2 架构内容 2.2.2.1 Azure Boards 2.2.2.2 Azure Repos 2.2.2.3 Azure Test Plans 2.2.2.4 Azure Pipelines 2.2.2.5 Azure Application Insights 2.2.2.6…

LLMs之Mistral:Mistral 7B v0.2的简介、安装和使用方法、案例应用之详细攻略

LLMs之Mistral&#xff1a;Mistral 7B v0.2的简介、安装和使用方法、案例应用之详细攻略 导读&#xff1a;Mistral AI首个7B模型发布于2023年9月&#xff0c;在基准测试中超越Llama 2 13B&#xff0c;一下子声名大振。Mistral 7B v0.2对应的指令调优版本Mistral-7B-Instruct-v0…

Topaz Video AI for mac 视频增强软件

Topaz Video AI for Mac是一款专为Mac用户设计的视频增强软件&#xff0c;它利用先进的人工智能技术和机器学习算法&#xff0c;为用户提供卓越的视频编辑和增强体验。 软件下载&#xff1a;Topaz Video AI for mac v4.2.2激活版 这款软件能够快速提高视频的清晰度、色彩饱和度…

【软考---系统架构设计师】特殊的操作系统介绍

目录 一、嵌入式系统&#xff08;EOS&#xff09; &#xff08;1&#xff09;嵌入式系统的特点 &#xff08;2&#xff09;硬件抽象层 &#xff08;3&#xff09;嵌入式系统的开发设计 二、实时操作系统&#xff08;RTOS&#xff09; &#xff08;1&#xff09;实时性能…