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

2023-12-10 08:20
文章标签 leetcode 指针 二分 查找 机器人 数目 预算内 2398

本文主要是介绍二分查找|双指针:LeetCode:2398.预算内的最多机器人数目，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

作者推荐

本文涉及的基础知识点

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

题目

你有 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

这篇关于二分查找|双指针:LeetCode:2398.预算内的最多机器人数目的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/476552。

相关文章

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...
hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。 解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2， 各自作为数组的下标，如果两部分相加为0，则满足等式； 代码如下： #include<iostream>#include<algorithm
阅读更多...
hdu2241（二分+合并数组）

hdu2241（二分+合并数组）

题意：判断是否存在a+b+c = x，a，b，c分别属于集合A,B,C 如果用暴力会超时，所以这里用到了数组合并，将b,c数组合并成d，d数组存的是b，c数组元素的和，然后对d数组进行二分就可以了 代码如下（附注释）： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que
阅读更多...
hdu2289（简单二分）

hdu2289（简单二分）

虽说是简单二分，但是我还是wa死了  题意：已知圆台的体积，求高度 首先要知道圆台体积怎么求：设上下底的半径分别为r1,r2,高为h,V = PI*(r1*r1+r1*r2+r2*r2)*h/3 然后以h进行二分 代码如下： #include<iostream>#include<algorithm>#include<cstring>#include<stack>#includ
阅读更多...
poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976： 题意： 在n场考试中，每场考试共有b题，答对的题目有a题。 允许去掉k场考试，求能达到的最高正确率是多少。 解析： 假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码： #include <iostream>#include <cstdio>#incl
阅读更多...
poj 3104 二分答案

poj 3104 二分答案

题意： n件湿度为num的衣服，每秒钟自己可以蒸发掉1个湿度。 然而如果使用了暖炉，每秒可以烧掉k个湿度，但不计算蒸发了。 现在问这么多的衣服，怎么烧事件最短。 解析： 二分答案咯。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c
阅读更多...
poj 3258 二分最小值最大

poj 3258 二分最小值最大

题意： 有一些石头排成一条线，第一个和最后一个不能去掉。 其余的共可以去掉m块，要使去掉后石头间距的最小值最大。 解析： 二分石头，最小值最大。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c
阅读更多...
poj 2594 二分图最大独立集

poj 2594 二分图最大独立集

题意： 求一张图的最大独立集，这题不同的地方在于，间接相邻的点也可以有一条边，所以用floyd来把间接相邻的边也连起来。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <sta
阅读更多...
poj 3692 二分图最大独立集

poj 3692 二分图最大独立集

题意： 幼儿园里，有G个女生和B个男生。 他们中间有女生和女生认识，男生男生认识，也有男生和女生认识的。 现在要选出一些人，使得这里面的人都认识，问最多能选多少人。 解析： 反过来建边，将不认识的男生和女生相连，然后求一个二分图的最大独立集就行了。 下图很直观： 点击打开链接 原图： 现图： 、 代码： #pragma comment(
阅读更多...
poj 2112 网络流+二分

poj 2112 网络流+二分

题意： k台挤奶机，c头牛，每台挤奶机可以挤m头牛。 现在给出每只牛到挤奶机的距离矩阵，求最小化牛的最大路程。 解析： 最大值最小化，最小值最大化，用二分来做。 先求出两点之间的最短距离。 然后二分匹配牛到挤奶机的最大路程，匹配中的判断是在这个最大路程下，是否牛的数量达到c只。 如何求牛的数量呢，用网络流来做。 从源点到牛引一条容量为1的边，然后挤奶机到汇点引一条容量为m的边
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2