消灭怪物的最大数量【力扣1921】
一、题目分析
需要满足的条件:
- 只能在每分钟的开始使用武器
- 武器能杀死距离城市最近的怪兽
- 怪兽到达城市就会输掉游戏
游戏最优策略:我们可以在每分钟的开始都使用一次武器,用来杀死距离城市最近的怪兽。这样可以在力所能及的范围内,杀死最多的怪兽。
二、测试用例分析

示例1中打怪兽的策略可以打死 3只怪兽,其实也可以换成这样的打法:
- 第 0 分钟开始时,怪物的距离是 [1,3,4],你消灭了第一个怪物。
- 第 1 分钟开始时,怪物的距离是 [X,2,3],你消灭了第二个怪物。
- 第 2分钟开始时,怪物的距离是 [X,X,2],你消灭了第三个怪物。
- 所有三个怪物都可以被消灭。
注意:我认为示例1中的方法不是“最优”策略。另外大家不要被这个示例误解,看第二步的时候,竟然没有消灭任何怪物,会误认为只有怪物和城市距离为1才能打死怪物;或者误认为只有在第i分钟内才能到达的怪物,才可以在i分钟时消灭。
三、解题策略
我们可以计算,每一个怪物最晚被消灭的时间,然后对时间进行排序。可以晚点消灭的怪物就会被排到后面。
例如dist=4,speed=2:
- 第 0 分钟开始时,怪物的距离是4,可以暂时不消灭
- 第 1 分钟开始时,怪物的距离是2,如果这时候不消灭的话,第2分钟开始时,怪物就到达城市,游戏失败了。
- 因此最晚消灭时间time=dist/speed-1=1;
例如dist=5,speed=2;
- 第 0 分钟开始时,怪物的距离是5,可以暂时不消灭
- 第 1 分钟开始时,怪物的距离是3,可以暂时不消灭
- 第 2 分钟开始时,怪物的距离是1,如果这时候不消灭的话,第3分钟开始时,怪物就到达城市,游戏失败了。
- 因此最晚消灭时间time=dist/speed=2;
总结:
- 若dist%speed==0:time=dist/speed-1;
- 否则:time=dist/speed;
四、示例代码
class Solution {
public:static bool cmp(int a,int b){return a<b;}int eliminateMaximum(vector<int>& dist, vector<int>& speed) {vector<int> time;for(int i=0;i<dist.size();i++){if(dist[i]%speed[i]==0){time.push_back(dist[i]/speed[i]-1);}else{time.push_back(dist[i]/speed[i]);}}sort(time.begin(),time.end(),cmp);int sum=0;for(int i=0;i<time.size();i++){if(i<=time[i]){sum++;}else{break;}}return sum;}
};相关文章:
消灭怪物的最大数量【力扣1921】
一、题目分析 需要满足的条件: 只能在每分钟的开始使用武器武器能杀死距离城市最近的怪兽怪兽到达城市就会输掉游戏 游戏最优策略:我们可以在每分钟的开始都使用一次武器,用来杀死距离城市最近的怪兽。这样可以在力所能及的范围内…...
数据结构之算法
算法的基本概念 计算机解题的过程实际上是在实施某种算法,这种算法称为计算机算法 算法的基本要素 一个算法是由两种基本要素组成:一是对数据对象的运算和操作;二是算法的控制结构 算法中对数据的运算和操作 在一般计算机系统中…...
MyBatis与MyBatis-Plus的分页以及转换
一、介绍 MyBatis和MyBatis-Plus都是Java持久化框架,用于简化数据库访问和操作。它们提供了面向对象的方式来管理关系型数据库中的数据。 MyBatis是一个轻量级的持久化框架,通过XML或注解配置,将SQL语句与Java对象进行映射,使开…...
TCP/IP网络编程(二) 套接字协议及其数据传输特性
文章目录 套接字协议及其数据传输特性关于协议创建套接字协议族套接字类型1:面向连接的套接字(SOCK_STREAM)套接字类型2:面向消息的套接字(SOCK_DGRAM)协议的最终选择面向连接的套接字:TCP套接字…...
在k8s中使用secret存储敏感数据与四种用法
当需要存储敏感数据时可以使用,secret会以密文的方式存储数据。 创建secret的四种方法 (1)通过--from-literal #每个--from-literal对应一个信息条目 kubectl create secret generic mysecret --from-literalusernameadmin --from-litera…...
国产10米分辨率的卫星介绍、下载和处理教程
10米分辨率的资源卫星介绍、下载和处理教程 简介 说起免费的10米分辨率卫星影像,大家首先想到的是sentinel卫星。但其实还有我国的中巴地球资源卫星04星(CBERS04)。 中巴地球资源卫星(China Brazil Earth Resources Satellite, CBERS)是中国和巴西共同投资、联合研制的地球…...
解决SpringBoot项目war部署到tomcat下无法Nacos中注册服务问题
问题说明 怎么解决Spring Boot项目部署到tomcat下无法Nacos中注册服务问题",希望能够解决您遇到有关问题。 在使用Nacos作为注册中心的Spring Boot项目,以war包形式部署到服务器上,启动项目发现该服务无法在Nacos中注册。 分析 …...
C++中的##、#符号含义
在C中,## 和 # 是两个不同的预处理符号。这些符号都是在C的预处理阶段使用的,用于在代码编译之前对文本进行操作。 #(字符串化操作符): 用于将宏参数转换为字符串常量。 #define STRINGIZE(x) #x const char* str S…...
探究Vue3中的Composition API:优化组件逻辑的新利器
一、toRef函数 在 Vue 3.0 中,引入了一种新的响应式 API,即 toRef。toRef 函数可以将一个普通值转换为响应式引用类型,这样就可以在模板中直接使用这个响应式引用类型的属性,并且当该属性发生变化时,视图会自动更新。 <templat…...
Google Services Framework 谷歌服务框架的安装以及遇到的常见问题
安装谷歌三件套: 1、Google 服务框架(Google Services Framework)下载地址: https://www.apkmirror.com/apk/google-inc/google-services-framework/ 注意一定要选择与自己手机对应的安卓系统版本的服务框架。 2、Google Play Se…...
学习高级数据结构:探索平衡树与图的高级算法
文章目录 1. 平衡树:维护数据的平衡与高效性1.1 AVL 树:严格的平衡1.2 红黑树:近似平衡 2. 图的高级算法:建模复杂关系与优化2.1 最小生成树:寻找最优连接方式2.2 拓扑排序:解决依赖关系 拓展思考 …...
centos7离线安装neo4j
一、准备需要的rpm包 本地环境执行如下命令: docker pull couchbase/centos7-systemd docker run -it couchbase/centos7-systemd bash # 可能需要换源 yum update -y vi /etc/yum.conf # 修改其中的keepcache1 rpm --import https://debian.neo4j.com/neotechnol…...
【黑马头条之项目部署_持续集成Jenkins】
本笔记内容为黑马头条项目的项目部署_持续集成部分 目录 一、内容介绍 1、什么是持续集成 2、持续集成的好处 3、今日内容 二、软件开发模式 1、软件开发生命周期 2、软件开发瀑布模型 3、软件的敏捷开发 三、Jenkins安装配置 1、Jenkins介绍 2、Jenkins环境搭建 …...
前端自动化部署,Devops,CI/CD
DevOps 提到 Jenkins,想到的第一个概念就是 CI/CD 在这之前应该再了解一个概念。 DevOps Development 和 Operations 的组合,是一种方法论,并不特指某种技术或者工具。DevOps 是一种重视 Dev 开发人员和 Ops 运维人员之间沟通、协作的流程。…...
22 元类技术(面向切片编程)|ORM的实现|抽象类与接口类
文章目录 前情知识补充hasattr 函数setattr函数getattr函数join 函数 元类技术使用type创建类什么是元类(概念总结)\_\_metaclass\_\_属性使用metaclass 的函数方式进行创建类使用metaclass 的类方式进行创建类 自定义元类 元类实现ORM接口类与抽象类抽象…...
fuchsia系统介绍
fuchsia系统 Fuchsia,是由Google公司开发的继Android和Chrome OS之后的第三个系统,已在Github中公开的部分源码可以得知。Google对于Fuchsia的说明是“Pink(粉红)Purple(紫色)Fuchsia(灯笼海棠…...
解决Jenkins执行Python脚本不能实时输出打印信息的问题
问题: 在使用Jenkins的shell command来执行python脚本时,总是会等脚本执行完毕,最后一次性才把脚本中的print语句给打印出来; 解决方法: 在print语句后加上sys.stdout.flush(), 就可以达到实时输出的目的了。...
2021年03月 C/C++(五级)真题解析#中国电子学会#全国青少年软件编程等级考试
C/C++编程(1~8级)全部真题・点这里 第1题:最小新整数 给定一个十进制正整数n(0 < n < 1000000000),每个数位上数字均不为0。n的位数为m。 现在从m位中删除k位(0<k < m),求生成的新整数最小为多少? 例如: n = 9128456, k = 2, 则生成的新整数最小为12456 时间…...
【微服务】服务发现和管理技术框架选型调研
选型背景 方案对比 结论 结合实际业务和开发需要,着重考虑性能可靠性、功能和社区支持程度三方面,认为Nacos更适合作为服务发现和管理的技术框架。具体理由如下: 性能更好,可靠性更高 经过阿里、APISIX、SpringCloudAlibaba,阿…...
【核磁共振成像】观共享重建
目录 一、K空间关键孔技术-数据采集二、BRISK技术三、TRICKS技术四、实时成像和滑动窗重建五、心电触发电影(CINE)采集六、分段心脏采集和观共享 一、K空间关键孔技术-数据采集 对于笛卡尔K空间,一个相位编码行有时称为一个K空间观。一般情况下,每帧图像…...
C++:std::is_convertible
C++标志库中提供is_convertible,可以测试一种类型是否可以转换为另一只类型: template <class From, class To> struct is_convertible; 使用举例: #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...
SCAU期末笔记 - 数据分析与数据挖掘题库解析
这门怎么题库答案不全啊日 来简单学一下子来 一、选择题(可多选) 将原始数据进行集成、变换、维度规约、数值规约是在以下哪个步骤的任务?(C) A. 频繁模式挖掘 B.分类和预测 C.数据预处理 D.数据流挖掘 A. 频繁模式挖掘:专注于发现数据中…...
【大模型RAG】Docker 一键部署 Milvus 完整攻略
本文概要 Milvus 2.5 Stand-alone 版可通过 Docker 在几分钟内完成安装;只需暴露 19530(gRPC)与 9091(HTTP/WebUI)两个端口,即可让本地电脑通过 PyMilvus 或浏览器访问远程 Linux 服务器上的 Milvus。下面…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
EtherNet/IP转DeviceNet协议网关详解
一,设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络,本网关连接到EtherNet/IP总线中做为从站使用,连接到DeviceNet总线中做为从站使用。 在自动…...
关键领域软件测试的突围之路:如何破解安全与效率的平衡难题
在数字化浪潮席卷全球的今天,软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件,这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下,实现高效测试与快速迭代?这一命题正考验着…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
在树莓派上添加音频输入设备的几种方法
在树莓派上添加音频输入设备可以通过以下步骤完成,具体方法取决于设备类型(如USB麦克风、3.5mm接口麦克风或HDMI音频输入)。以下是详细指南: 1. 连接音频输入设备 USB麦克风/声卡:直接插入树莓派的USB接口。3.5mm麦克…...
