LCP 30. 魔塔游戏
LCP 30. 魔塔游戏
难度: 中等
题目:
小扣当前位于魔塔游戏第一层,共有
N
个房间,编号为0 ~ N-1
。每个房间的补血道具/怪物对于血量影响记于数组nums
,其中正数表示道具补血数值,即血量增加对应数值;负数表示怪物造成伤害值,即血量减少对应数值;0
表示房间对血量无影响。小扣初始血量为 1,且无上限。假定小扣原计划按房间编号升序访问所有房间补血/打怪,为保证血量始终为正值,小扣需对房间访问顺序进行调整,每次仅能将一个怪物房间(负数的房间)调整至访问顺序末尾。请返回小扣最少需要调整几次,才能顺利访问所有房间。若调整顺序也无法访问完全部房间,请返回 -1。
提示:
1 <= nums.length <= 10^5
-10^5 <= nums[i] <= 10^5
示例 1:
输入:
nums = [100,100,100,-250,-60,-140,-50,-50,100,150]
输出:
1
解释:初始血量为 1。至少需要将 nums[3] 调整至访问顺序末尾以满足要求。
分析
如果全部和加起来是小于等于0的,那么不管怎么排都是不能访问到所有房间的,所以我们可以首先求一下全部的和,注意要开long long
,大于0的话就是一定有解的,因为最坏情况我们可以将所有的负数调整到 最后,这样就一定可以全部访问完,那么怎么来求最少要交换多少次呢,如果当前的血量是负数,我们就肯定需要将怪物往后挪,挪哪个怪物呢,因为要挪动次数最少,所以我们考虑挪动前面最厉害的怪物,也就是nums[]
最小的,可以证明,这样做是最优的,依次这样访问就可以了,那么怎么快速得到最小的nums[]
呢,我们可以用堆数据结构,是小根堆,,cpp可以使用priority_queue<int, vector<int>, greater<int>>
, 这样我们就可以在logn
的时间获得最小值,总体时间复杂度是nlogn
因为每个元素最多就是进入小根堆1一次
优先队列 + 贪心
class Solution {
public:using LL = long long;int magicTower(vector<int>& nums) {LL sum = accumulate(nums.begin(), nums.end(), 1ll);if (sum <= 0) return -1;int n = nums.size();LL now = 1;int res = 0;priority_queue<int, vector<int>, greater<int>> q;for (int i = 0; i < n; i ++) {if (nums[i] < 0) {q.push(nums[i]);}now += nums[i];if (now <= 0) {res ++;now -= q.top();q.pop();}}return res;}
};
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)
结束了
相关文章:
LCP 30. 魔塔游戏
LCP 30. 魔塔游戏 难度: 中等 题目: 小扣当前位于魔塔游戏第一层,共有 N 个房间,编号为 0 ~ N-1。每个房间的补血道具/怪物对于血量影响记于数组 nums,其中正数表示道具补血数值,即血量增加对应数值;负数表示怪物造…...
RCE(命令执行)知识点总结最详细
description: 这里是CTF做题时常见的会遇见的RCE的漏洞知识点总结。 如果你觉得写得好并且想看更多web知识的话可以去gitbook.22kaka.fun去看,上面是我写的一本关于web学习的一个gitbook,当然如果你能去我的github为我的这个项目点亮星星我会感激不尽htt…...
[英语学习][27][Word Power Made Easy]的精读与翻译优化
[序言] 译者的这次翻译非常好. 对what与从句的嵌套用法, 进行了精准的翻译. 这次的记录, 也是对我自己的一次翻译经验的提升. 但是唯一遗憾的是"derivation"没有翻译好. [英文学习的目标] 提升自身的英语水平, 对日后编程技能的提升有很大帮助. 希望大家…...
Jupyter Notebook如何在E盘打开
Jupyter Notebook如何在E盘打开 方法1:方法2: 首先打开Anaconda Powershell Prompt, 可以看到默认是C盘。 可以对应着自己的界面输入: 方法1: (base) PS C:\Users\bella> E: (base) PS E:\> jupyter notebook方法2&#x…...
显示器校准软件:BetterDisplay Pro for Mac v2.0.11激活版下载
BetterDisplay Pro是一款由waydabber开发的Mac平台上的显示器校准软件,可以帮助用户调整显示器的颜色和亮度,以获得更加真实、清晰和舒适的视觉体验。 软件下载: BetterDisplay Pro for Mac v2.0.11激活版下载 以下是BetterDisplay Pro的主要…...
【第六天】c++虚函数多态
一、多态的概述 多态按字面的意思就是多种形态。当类之间存在层次结构,并且类之间是通过继承关联(父类与子类)时,就会用到多态。 C 多态意味着调用成员函数时,会根据调用函数的对象的类型来执行不同的函数。 静态多态&…...
CGAL::2D Arrangements-3
3.Arrangement查询 Arrangement里面最重要的查询操作是point-location,给定一个点,查找到包含这个点的Arrangement。通常情况下,point-location查询得到的结果是Arrangement的一个face,退化情况下会是一个edge,查一个…...
机器学习--K近邻算法,以及python中通过Scikit-learn库实现K近邻算法API使用技巧
文章目录 1.K-近邻算法思想2.K-近邻算法(KNN)概念3.电影类型分析4.KNN算法流程总结5.k近邻算法api初步使用机器学习库scikit-learn1 Scikit-learn工具介绍2.安装3.Scikit-learn包含的内容4.K-近邻算法API5.案例5.1 步骤分析5.2 代码过程 1.K-近邻算法思想 假如你有一天来到北京…...
Redis 使用 RDB 持久化方式的过程
定时触发: RDB 持久化是通过设置一个定时触发的机制来进行的。管理员可以配置 Redis 在经过一定时间间隔或执行了一定数量的写操作后触发 RDB 持久化。这个配置通常在 Redis 的配置文件中进行,可以通过 save 或 save 900 1 这样的配置项来设定。 save 90…...
仰暮计划|“我非常感谢党的领导,作为一名普通百姓,我也愿意为国家的发展继续贡献微薄的力量”
她出生于1945年,现居河南省平顶山市宝丰县城关镇东街社区,是一位和蔼可亲的老人。 孙奶奶回忆,在学生时期,是点蜡烛照明的,打瞌睡或者离作业本近的时候,就会烧到头发,当时的作业量不大ÿ…...
【思科ssh】思科模拟器配置ssh登录
配置路由器的名称为R1 配置路由器的域名为aaa.com 使用rsa来加密传输数据,密钥位数为2048 配置登录用户名为cj,密码为123456 只允许ssh登录,不能以其他方式登录 本地验证...
python创建pdf文件
目录 一:使用reportlab库 二:使用使pdf库 在Python中生成PDF文件可以使用多种库,其中最常用的是reportlab和fpdf。以下是使用这两个库生成PDF文件的示例代码: 一:使用reportlab库 1:写入文字信息 from r…...
ubuntu开机报错/dev/nume0n1p2:clean
TOC 一、前提 1、当你平时用的图站或者linux系统出现这个问题,首先看看你的显卡有没有换位置。 我的就是项目电脑,同事换了显卡位置,我不知道,当我在这个基础上继续做的时候,出了问题。 2、当你是第一次装显卡&…...
openstack(T版)公有云--Dashboard服务
公有云上OpenStack Train最小化安装_openstack最小化部署-CSDN博客 我的opensatck(T)是参考上面链接去部署完成的,在部署完Dashboard服务后,将要用浏览器访问的时候出现了404 500 Internal Server Error 等各种各样的问题,以下是我排查问题…...
Vue ElementUI中el-table表格嵌套样式问题
一、表格嵌套要求: 两个表格嵌套,当父表格有children数组时子表格才展示;子表格数据少于父表格展示字段,且对应固定操作列不同; 二、嵌套问题: 当使用el-table的typeexpand实现表格嵌套时,样…...
ssm+vue的校园一卡通密钥管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。
演示视频: ssmvue的校园一卡通密钥管理系统(有报告)。Javaee项目,ssm vue前后端分离项目。 项目介绍: 采用M(model)V(view)C(controller)三层体系…...
docker进阶 问题1
如何使用Docker的容器调试和故障排查工具? Docker提供了一系列强大的工具来帮助开发者调试和排查容器中的问题。以下是一些关键步骤和工具的使用方法: 查看容器日志:使用docker logs [容器ID或名称]命令可以轻松查看容器的标准输出和错误。…...
【OpenVINO™】在 MacOS 上使用 OpenVINO™ C# API 部署 Yolov5 (下篇)
在 MacOS 上使用 OpenVINO™ C# API 部署 Yolov5 (下篇) 项目介绍 YOLOv5 是革命性的 "单阶段"对象检测模型的第五次迭代,旨在实时提供高速、高精度的结果,是世界上最受欢迎的视觉人工智能模型,代表了Ult…...
使用CHATGPT进行论文写作的缺点和风险
为了真正感受 ChatGPT 的写作潜力,让我们先将其与传统的论文写作方法进行一下比较分析 CHATGPT论文写作的缺点和风险 传统论文写作的考验和磨难很深:费力的研究、组织想法和精心设计的逻辑论证,往往以牺牲你的理智为代价。 进入ChatGPT&am…...
【Android-Gradle】多模块开发中,定义额外属性(全局变量),穿梭在不同的Gradle文件中(kotlin脚本版)
其他信息可以参考官网:https://docs.gradle.org/current/dsl/org.gradle.api.plugins.ExtraPropertiesExtension.html#org.gradle.api.plugins.ExtraPropertiesExtension 但是本文讲一些简单应用: 需求1:根目录gradle文件定义一个全局变量 …...
React18原理: Fiber架构下的单线程CPU调度策略
概述 React 的 Fiber 架构, 它的整个设计思想就是去参考CPU的调度策略CPU现在都是多核多进程的,重点研究的是 CPU是单核单线程,它是如何调度的?为什么要去研究单线程的CPU? 浏览器中的JS它是单线程的JS 的执行线程和浏览器的渲染GUI 是互斥…...
个人搜集的gstreamer学习链接
gstreamer资源: GStreamer: 官方英文官网 GStreamer C开发教程 (gstreamer安装包下载目录) GStreamer GitLab源码 gstreamer 插件列表) gstreamer官方文档: https://gstreamer.freedesktop.org/documentation/tutorials/index.html?gi-languagec …...
Blazor Wasm Gitee 码云登录
目录: OpenID 与 OAuth2 基础知识Blazor wasm Google 登录Blazor wasm Gitee 码云登录Blazor SSR/WASM IDS/OIDC 单点登录授权实例1-建立和配置IDS身份验证服务Blazor SSR/WASM IDS/OIDC 单点登录授权实例2-登录信息组件wasmBlazor SSR/WASM IDS/OIDC 单点登录授权实例3-服务端…...
Android 自定义BaseActivity
直接上代码: BaseActivity代码: package com.example.custom.activity;import android.annotation.SuppressLint; import android.app.Activity; import android.content.pm.ActivityInfo; import android.os.Bundle; import android.os.Looper; impor…...
基于鲲鹏服务器的LNMP配置
基于鲲鹏服务器的LNMP配置 系统 Centos8 # cat /etc/redhat-release CentOS Linux release 8.0.1905 (Core) 卸载已经存在的旧版本的安装包 # rpm -qa | grep php #查看已经安装的PHP旧版本# rpm -qa | grep php | xargs rpm -e #卸载已经安装的旧版,如果提示有…...
MIT-Missing Semester_Topic 6:Version Control (Git) 练习题
文章目录 练习一练习二练习三练习四练习五练习六练习七 练习一 若还没有 Git 的相关经验,阅读 Pro Git 的前几章或诸如 Learn Git Branching 的相关教程,并在学习的同时从 Git 的数据模型(data model)的角度思考各 Git 命令。 老师…...
OpenHarmony轻量级内核-LiteOS-M
OpenHarmony轻量级内核 思维导图 https://download.csdn.net/download/lanlingxueyu/88816723 概述 内核是一人操作系统的运算核心,决定着系统的性能和稳定性。它是基于硬件的第一层软件扩充,提供操作系统的基本功能,是操作系统工作的基础。它负责管理系统的进程、内存、…...
TCP 传输控制协议——详细
目录 1 TCP 1.1 TCP 最主要的特点 1.2 TCP 的连接 TCP 连接,IP 地址,套接字 1.3 可靠传输的工作原理 1.3.1 停止等待协议 (1)无差错情况 (2)出现差错 (3)确认丢失和确认迟到…...
ArcGIS学习(六)地理数据库
ArcGIS学习(六)地理数据库 上个任务我们讲了一个非常重要的知识点一一坐标系。这个任务我们带来另外一个很重要的知识点一一地理数据库。 地理数据库的内容相比于坐标系简单很多! 首先,先让我们来学习下地理数据库的理论。 ArcGIS 中的地理数据库(Geodatabase)是一个用…...
保研机试算法训练个人记录笔记(四)——哈希算法
目录 两数之和 字母异位词分组 最长连续序列 力扣热题100——哈希算法 两数之和 给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。 你可以假设每种输入只会对应一个答…...
ChatGPT实战100例 - (14) 打造AI编程助手 Code Copilot
文章目录 ChatGPT实战100例 - (14) 打造AI编程助手 Code Copilot一、Code Copilot AI编程助手二、制作代码生成器2.1 定义生成器框架2.2 从现有代码提取代码模板三、进行代码优化ChatGPT实战100例 - (14) 打造AI编程助手 Code Copilot 一、Code Copilot AI编程助手 Code Copi…...
表单标记(html)
前言 发现input的type属性还是有挺多的,这里把一些常用的总结一下。 HTML 输入类型 (w3school.com.cn)https://www.w3school.com.cn/html/html_form_input_types.asp text-文本 文本输入,如果文字太长,超出的部分就不会显示。 定义供文本输入的单行…...
Linux文件和目录管理
目录基础 Linux操作系统以目录的方式来组织和管理系统中的所有文件。所谓的目录,就是将所有文件的说明信息采用树状结构组织起来。每个目录节点之下会有文件和子目录。 所有一切都从 ‘根’ 开始,用 ‘/’ 代表, 并且延伸到子目录。 bin:B…...
【go】gorm\xorm\ent事务处理
文章目录 1 gorm1.1 开启事务1.2 执行操作1.3 提交或回滚 2 xorm2.1 开启事务2.2 执行操作2.3 提交或回滚 3 ent3.1 开启事务3.2 执行操作3.3 提交或回滚 前言:本文介绍golang三种orm框架对数据库事务的操作 1 gorm Begin开启事务 tx *gorm.DB 1.1 开启事务 tx :…...
【数据分享】1929-2023年全球站点的逐月平均风速(Shp\Excel\免费获取)
气象数据是在各项研究中都经常使用的数据,气象指标包括气温、风速、降水、能见度等指标,说到气象数据,最详细的气象数据是具体到气象监测站点的数据! 有关气象指标的监测站点数据,之前我们分享过1929-2023年全球气象站…...
IP地址详解
IP地址是互联网协议(Internet Protocol)用于标识并定位网络中主机(如计算机、服务器、路由器等)的一串数字。它是一个32位的二进制数,通常以四个数字(每个数字范围为0-255)的形式显示࿰…...
Python爬虫http基本原理#2
Python爬虫逆向系列(更新中):http://t.csdnimg.cn/5gvI3 HTTP 基本原理 在本节中,我们会详细了解 HTTP 的基本原理,了解在浏览器中敲入 URL 到获取网页内容之间发生了什么。了解了这些内容,有助于我们进一…...
Web Services 服务 是不是过时了?创建 Web Services 服务实例
Web Services 是不是过时了? 今天是兔年最后一天,先给大家拜个早年 。 昨天上午视频面试一家公司需要开发Web Services 服务,这个也没有什么,但还需要用 VB.net 开发。这个是多古老的语言了,让我想起来了 10年 前 写 …...
redis单线程还快的原因
1. 内存存储和高效数据结构: 内存存储: Redis将数据存储在内存中,因此可以实现非常高的读写速度,而无需频繁的磁盘I/O操作。 高效数据结构: Redis内置了丰富且高效的数据结构,如字符串、哈希表、列表、集合…...
【flutter】报错 cmdline-tools component is missing
在flutterSDK目录下,双击flutter_console.bat,调出命令行。 输入flutter doctor,如果第三个诊断为[x],报cmdline-tools component is missing错(我这已经修改好了,所以是勾了),那就可…...
以用户为中心,酷开科技荣获“消费者服务之星”
在企业顺应消费升级的道路中,企业自身不仅要着力强化对于消费者服务意识的提升,并且要树立诚信自律的行业示范带头作用,助力消费环境稳中向好,不断满足人民群众对美好生活的期待。企业的发展需要消费者的认可,酷开科技…...
Days 27 ElfBoard 板 AltiumDesigner 相同电路快速布局布线
在进行设计开发的时候,总会遇到相同的电路,或者模块,这些电路可以使用相同的布局和走线,例如 DC-DC 电源、网口 PHY 电路部分。这类型的电路,我们可以采用AltiumDesigner 中的 Room 进行布局和布线的快速复制ÿ…...
除夕快乐(前端小烟花)
家人们,新的一年好运常在,愿大家在新的一年里得偿所愿,发财暴富,愿大家找到属于自己的那个公主,下面就给大家展示一下给公主的烟花 前端烟花 新的一年,新的挑战,愿我们不忘初心,砥砺…...
fast.ai 深度学习笔记(二)
深度学习 2:第 1 部分第 4 课 原文:medium.com/hiromi_suenaga/deep-learning-2-part-1-lesson-4-2048a26d58aa 译者:飞龙 协议:CC BY-NC-SA 4.0 来自 fast.ai 课程的个人笔记。随着我继续复习课程以“真正”理解它,这…...
风行智能电视G32Y 强制刷机升级方法,附刷机升级数据MstarUpgrade.bin
升级步骤: 1、下载刷机数据,如是压缩包,需要先解压,然后将刷机bin格式的文件重命名为MstarUpgrade.bin 2、将此文件放到U盘根目录 (U盘格式FAT32,单分区,建议4G的优盘刷机成功率高)…...
tsgctf-2021-lkgit-无锁竞争-userfaultfd
启动脚本 qemu-system-x86_64 \-kernel ./bzImage \-initrd ./rootfs.cpio \-nographic \-monitor /dev/null \-cpu kvm64,smep,smap \-append "consolettyS0 kaslr oopspanic panic1 quiet" \-no-reboot \-m 256M题目 lkgit_hash_object #define HASH_SIZE …...
物联网数据隐私保护技术
在物联网(IoT)的世界中,无数的设备通过互联网连接在一起,不断地收集、传输和处理数据。这些数据有助于提高生产效率、优化用户体验并创造新的服务模式。然而,随着数据量的剧增,数据隐私保护成为了一个不能忽…...
RabbitMQ-1.介绍与安装
介绍与安装 1.RabbitMQ1.0.技术选型1.1.安装1.2.收发消息1.2.1.交换机1.2.2.队列1.2.3.绑定关系1.2.4.发送消息 1.2.数据隔离1.2.1.用户管理1.2.3.virtual host 1.RabbitMQ 1.0.技术选型 消息Broker,目前常见的实现方案就是消息队列(MessageQueue&…...
CSS高级技巧
一、 精灵图 1.1 为什么需要精灵图? 1.2 精灵图(sprites)的使用 二、 字体图标 2.1 字体图标的产生 2.2 字体图标的优点 2.3 字体图标的下载 icomoom字库 http://icomoon.io 阿里iconfont字库 http://www.iconfont.cn/ 2.4 字体图标的引用…...
Redis的数据类型Hash使用场景实战
Redis的数据类型Hash使用场景 常见面试题:redis在你们项目中是怎么用的,除了String数据类型还使用什么数据类型? 怎么保证缓存和数据一致性等问题… Hash模型使用场景 知识回顾: redisTemplate.opsForHash() 方法是 Redis 的 …...