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文件定义一个全局变量 …...
浅谈 React Hooks
React Hooks 是 React 16.8 引入的一组 API,用于在函数组件中使用 state 和其他 React 特性(例如生命周期方法、context 等)。Hooks 通过简洁的函数接口,解决了状态与 UI 的高度解耦,通过函数式编程范式实现更灵活 Rea…...
使用VSCode开发Django指南
使用VSCode开发Django指南 一、概述 Django 是一个高级 Python 框架,专为快速、安全和可扩展的 Web 开发而设计。Django 包含对 URL 路由、页面模板和数据处理的丰富支持。 本文将创建一个简单的 Django 应用,其中包含三个使用通用基本模板的页面。在此…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...
(二)TensorRT-LLM | 模型导出(v0.20.0rc3)
0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述,后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作,其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...
【论文笔记】若干矿井粉尘检测算法概述
总的来说,传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度,通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...
uniapp微信小程序视频实时流+pc端预览方案
方案类型技术实现是否免费优点缺点适用场景延迟范围开发复杂度WebSocket图片帧定时拍照Base64传输✅ 完全免费无需服务器 纯前端实现高延迟高流量 帧率极低个人demo测试 超低频监控500ms-2s⭐⭐RTMP推流TRTC/即构SDK推流❌ 付费方案 (部分有免费额度&#x…...
图表类系列各种样式PPT模版分享
图标图表系列PPT模版,柱状图PPT模版,线状图PPT模版,折线图PPT模版,饼状图PPT模版,雷达图PPT模版,树状图PPT模版 图表类系列各种样式PPT模版分享:图表系列PPT模板https://pan.quark.cn/s/20d40aa…...
JavaScript 数据类型详解
JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型(Primitive) 和 对象类型(Object) 两大类,共 8 种(ES11): 一、原始类型(7种) 1. undefined 定…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
Python 实现 Web 静态服务器(HTTP 协议)
目录 一、在本地启动 HTTP 服务器1. Windows 下安装 node.js1)下载安装包2)配置环境变量3)安装镜像4)node.js 的常用命令 2. 安装 http-server 服务3. 使用 http-server 开启服务1)使用 http-server2)详解 …...
