二分查找|双指针:LeetCode:2398.预算内的最多机器人数目

作者推荐

【动态规划】【广度优先】LeetCode2258:逃离火灾

本文涉及的基础知识点

二分查找算法合集
滑动窗口
单调队列:计算最大值时,如果前面的数小,则必定被淘汰,前面的数早出队。

题目

你有 n 个机器人,给你两个下标从 0 开始的整数数组 chargeTimes 和 runningCosts ,两者长度都为 n 。第 i 个机器人充电时间为 chargeTimes[i] 单位时间,花费 runningCosts[i] 单位时间运行。再给你一个整数 budget 。
运行 k 个机器人 总开销 是 max(chargeTimes) + k * sum(runningCosts) ,其中 max(chargeTimes) 是这 k 个机器人中最大充电时间,sum(runningCosts) 是这 k 个机器人的运行时间之和。
请你返回在 不超过 budget 的前提下,你 最多 可以 连续 运行的机器人数目为多少。
示例 1:
输入:chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
输出:3
解释:
可以在 budget 以内运行所有单个机器人或者连续运行 2 个机器人。
选择前 3 个机器人,可以得到答案最大值 3 。总开销是 max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 ,小于 25 。
可以看出无法在 budget 以内连续运行超过 3 个机器人,所以我们返回 3 。
示例 2:
输入:chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
输出:0
解释:即使运行任何一个单个机器人,还是会超出 budget,所以我们返回 0 。
参数范围
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015

双指针

分析

本质是子数组,我们可以枚举起点left ,子数组[left,righ)是不超预算的最长子数组。

时间复杂度

O(n),枚举left和right都是O(n),right没有从新开始,所有总时间复杂度是O(n)。

代码

核心代码

class Solution {
public:
int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) {
m_c = chargeTimes.size();
int iRet = 0;
long long llSum = 0;
std::deque vMaxIndex;
for (int left = 0, right = 0; left < m_c; left++)
{
if (right < left)
{
llSum = 0;
right = left;
vMaxIndex.clear();
}
while (right < m_c)
{
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[right]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(right);
const long long llNew = (llSum + runningCosts[right]) * (right-left+1) + chargeTimes[vMaxIndex.front()];
if (llNew > budget)
{
break;// [left,right)超出预算,有多个right,取最小的按个
}
llSum += runningCosts[right];
right++;
}
iRet = max(iRet, right - left);
llSum -= runningCosts[left];
if (vMaxIndex.front() == left)
{
vMaxIndex.pop_front();
}
}
return iRet;
}
int m_c;
};

测试用例

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){assert(v1[i] == v2[i]);}
}template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}int main()
{vector<int> chargeTimes, runningCosts;long long budget;{Solution slu;chargeTimes = { 3,6,1,3,4 }, runningCosts = { 2,1,3,4,5 }, budget = 25;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(3, res);}{Solution slu;chargeTimes = { 11,12,19 }, runningCosts = { 10,8,7 }, budget = 19;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 0);}{Solution slu;chargeTimes = { 19,63,21,8,5,46,56,45,54,30,92,63,31,71,87,94,67,8,19,89,79,25 }, runningCosts = { 91,92,39,89,62,81,33,99,28,99,86,19,5,6,19,94,65,86,17,10,8,42 }, budget = 85;auto res = slu.maximumRobots(chargeTimes, runningCosts, budget);Assert(res, 1);}//CConsole::Out(res);
}

优化

如果不存在以left开始的合法子数组,right和left相同,left++后,right就小于left ,需要特殊处理。
我们换成先枚举right,再枚举left。左闭右闭空间[left,right]是最长合法子数组。但不存在合法子数组时:left等于right+1,right++后,两者就相等了,无需特殊处理。

代码

class Solution {
public:int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {m_c = chargeTimes.size();int iRet = 0;long long llSum = 0;std::deque<int> vMaxIndex;for (int right = 0, left = 0; right < m_c; right++){	while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[right])){vMaxIndex.pop_back();				}vMaxIndex.emplace_back(right);llSum += runningCosts[right];while (left <= right ){		const long long llNew = llSum * (right-left+1) + chargeTimes[vMaxIndex.front()];if (llNew > budget){llSum -= runningCosts[left];if (vMaxIndex.front() == left){vMaxIndex.pop_front();}left++;}else{break;}}iRet = max(iRet, right - left+1);			}return iRet;}int m_c;
};

二分查找

寻找最后一个不超预算的连续机器人长度,左开右闭。时间复杂度😮(longnn)。二分长度,时间复杂度度O(logn);指定长度枚举所有终点,时间复杂度O(n)。

代码

class Solution {
public:
int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) {
m_c = chargeTimes.size();
int left = 0, right = m_c + 1;
while (right - left > 1)
{
const auto mid = left + (right - left) / 2;
if (NeedBudget(chargeTimes, runningCosts, mid) <= budget)
{
left = mid;
}
else
{
right = mid;
}
}
return left;
}
long long NeedBudget(vector& chargeTimes, vector& runningCosts, int len)
{
long long llSum = 0;
std::deque vMaxIndex;
int i = 0;
for (; i < len; i++)
{
llSum += runningCosts[i];
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[i]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(i);
}
long long llNeed = llSum * len + chargeTimes[vMaxIndex.front()];
for (; i < m_c; i++)
{
llSum += runningCosts[i]- runningCosts[i-len];
while (vMaxIndex.size() && (chargeTimes[vMaxIndex.back()] <= chargeTimes[i]))
{
vMaxIndex.pop_back();
}
vMaxIndex.emplace_back(i);
if (vMaxIndex.front() == i-len)
{
vMaxIndex.pop_front();
}
llNeed = min(llNeed,llSum * len + chargeTimes[vMaxIndex.front()]);
}
return llNeed;
}
int m_c;
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业

。也就是我们常说的专业的人做专业的事。 |
|如果程序是一条龙,那算法就是他的是睛|

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境:

VS2022 C++17

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

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

相关文章

锁--07_2---- index merge(索引合并)引起的死锁

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 案例分析生产背景死锁日志表结构执行计划 EXPLAN为什么会用 index_merge&#xff08;索引合并&#xff09;为什么用了 index_merge就死锁了解决方案注&#xff1a;M…

初识Pandas函数是Python的一个库(继续更新...)

学习网页&#xff1a; Welcome to Python.orghttps://www.python.org/https://www.python.org/https://www.python.org/ Pandas函数库 Pandas是一个Python库&#xff0c;提供了大量的数据结构和数据分析工具&#xff0c;包括DataFrame和Series等。Pandas的函数非常丰富&…

Spring Boot3.1.6配置对应的Swagger

1. pom.xml导入Swagger依赖 <!--swagger3--> <dependency><groupId>org.springdoc</groupId><artifactId>springdoc-openapi-starter-webmvc-ui</artifactId><version>2.0.2</version> </dependency> 2.创建SwaggerCo…

自动化访客互动:提升网站效益与用户体验的关键优势

在激烈的市场竞争环境中&#xff0c;想抢占市场&#xff0c;获得收益并不容易。每一个订单的完成都要经过一定的销售周期&#xff0c;所以企业可以根据销售周期每个阶段的特点进行优化&#xff0c;留住客户。其中&#xff0c;企业可以在与客户在线互动的过程中&#xff0c;让互…

【第2期】Springboot如何快速集成SpringSecurity

简单介绍 本专栏主要结合实战讲解&#xff0c;不过多介绍细节的概念&#xff0c;概念可以通过搜索引擎查找&#xff0c;一搜一大把&#xff0c;切入正题。 本专栏的实战项目是基于SpringbootSpringSecurityRSAJWTVUE的全栈开发项目&#xff0c;每个环节都会专门讲&#xff0c;…

C语言 文件I/O(备查)

所有案列 跳转到其他。 文件打开 FILE* fopen(const char *filename, const char *mode); 参数&#xff1a;filename&#xff1a;指定要打开的文件名&#xff0c;需要加上路径&#xff08;相对、绝对路径&#xff09;mode&#xff1a;指定文件的打开模式 返回值&#xff1a;成…

遥感图像分割系统:融合空间金字塔池化(FocalModulation)改进YOLOv8

1.研究背景与意义 项目参考AAAI Association for the Advancement of Artificial Intelligence 研究背景与意义 遥感图像分割是遥感技术领域中的一个重要研究方向&#xff0c;它的目标是将遥感图像中的不同地物或地物类别进行有效的分割和识别。随着遥感技术的不断发展和遥感…

2024年高效远程协同运维工具推荐

随着企业的不断发展以及变化&#xff0c;企业的内部IT环境也是日益复杂&#xff0c;一跨高效远程协同运维工具必不可少&#xff0c;不仅可以提高生产力&#xff0c;还能降低运营成本。这里就给大家推荐2024年高效远程协同运维工具。 高效远程协同运维工具应用场景 1、IT运维管…

(五)STM32 按键输入实验及 GPIO做普通 IO 的注意事项

目录 1. 按键硬件连接 2. 按键软件设计 3. 按键消抖 4. 使用 IO 口时的 注意事项&#xff08;踩坑&#xff09; 上一节我们介绍了 STM32F1 的 IO 口作为输出的使用&#xff0c;这一章&#xff0c;我们将介绍如何使用 STM32F1 的 IO 口作为输入用。在本章中&#xff0c;我们…

modbus 通信协议介绍与我的测试经验分享

1、简介 Modbus 协议是一种通信协议&#xff0c;用于工业自动化系统中的设备间通信。该协议最初由 Modicon 公司开发&#xff0c;并于 1979 年发布。 Modbus 协议通过串行通信格式进行通信&#xff0c;在物理层上支持 RS-232、RS-422 和 RS-485 等多种通信方式。在协议层面&am…

Guardrails for Amazon Bedrock 基于具体使用案例与负责任 AI 政策实现定制式安全保障(预览版)

作为负责任的人工智能&#xff08;AI&#xff09;战略的一部分&#xff0c;您现在可以使用 Guardrails for Amazon Bedrock&#xff08;预览版&#xff09;&#xff0c;实施专为您的用例和负责任的人工智能政策而定制的保障措施&#xff0c;以此促进用户与生成式人工智能应用程…

redis未授权漏洞复现

什么是redis redis就是个数据库&#xff0c;跟mysql不同的地方在于redis主要将数据存在内存中&#xff0c;读写速度非常快 redis未授权 其原因很简单&#xff0c;就是redis服务器在默认安装好不配置的情况下可以直接免密码登录&#xff0c;登录后在web目录写入一句话木马&am…

【Spark精讲】RDD特性之数据本地化

目录 首选运行位置 数据的本地化级别 谁来负责数据本地化 数据本地化执行流程 调优 代码中的设置方法 首选运行位置 上图红框为RDD的特性五&#xff1a;每个RDD的每个分区都有一组首选运行位置&#xff0c;用于标识RDD的这个分区数据最好能够在哪台主机上运行。通过RDD的…

亚信科技AntDB数据库——深入了解AntDB-M元数据锁的相关概念

AntDB-M在架构上分为两层&#xff0c;服务层和存储引擎层。元数据的并发管理集中在服务层&#xff0c;数据的存储访问在存储引擎层。为了保证DDL操作与DML操作之间的一致性&#xff0c;引入了元数据锁&#xff08;MDL&#xff09;。 AntDB-M提供了丰富的元数据锁功能&#xff…

leetcode 236. 二叉树的最近公共祖先

leetcode 236. 二叉树的最近公共祖先 题目 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为&#xff1a;“对于有根树 T 的两个节点 p、q&#xff0c;最近公共祖先表示为一个节点 x&#xff0c;满足 x 是 p、q 的祖先且 x 的深度尽…

4G无线工业级路由器在智能制造设备互联互通中的角色

随着工业技术的不断发展和进步&#xff0c;智能制造已经成为了现代制造业的重要趋势和发展方向。而在智能制造过程中&#xff0c;设备之间的互联互通是至关重要的一环。在这个过程中&#xff0c;4G无线工业级路由器扮演着重要的角色&#xff0c;它提供了稳定可靠的网络连接&…

Vue3项目中集成mars3D简单三部曲

Vue3项目中集成mars3D简单三部曲 这里是参考网址&#xff0c;大佬可以点击一件跳转 1.安装依赖 npm install vite-plugin-mars3d --save-dev2.修改 vite.config.ts 配置文件 import { defineConfig } from vite; import { mars3dPlugin } from vite-plugin-mars3d;export d…

Go开发运维:Go服务发布到K8S集群

目录 一、实验 1.Go服务发布到k8s集群 二、问题 1.如何从Harbor拉取镜像 一、实验 1.Go服务发布到k8s集群 &#xff08;1&#xff09;linux机器安装go(基于CentOS 7系统) yum install go -y &#xff08;2&#xff09;查看版本 go version &#xff08;3&#xff09;创…

vue3 setup语法糖写法基本教程

前言 官网地址&#xff1a;Vue.js - 渐进式 JavaScript 框架 | Vue.js (vuejs.org)下面只讲Vue3与Vue2有差异的地方&#xff0c;一些相同的地方我会忽略或者一笔带过与Vue3一同出来的还有Vite&#xff0c;但是现在不使用它&#xff0c;等以后会有单独的教程使用。目前仍旧使用v…

GZ015 机器人系统集成应用技术样题3-学生赛

2023年全国职业院校技能大赛 高职组“机器人系统集成应用技术”赛项 竞赛任务书&#xff08;学生赛&#xff09; 样题3 选手须知&#xff1a; 本任务书共 26页&#xff0c;如出现任务书缺页、字迹不清等问题&#xff0c;请及时向裁判示意&#xff0c;并进行任务书的更换。参赛队…