本文涉及的基础知识点
C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
单调双向队列
题目
你有 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
分析
时间复杂度
两层循环，但第二层循环，没有从头开始。所以总时间复杂度是O(n)。
滑动窗口
[left,r)如果r增加，则预算也增加。对于每个left，我们求出使[left,r]超过预算的第一个r，也就是[left,r)以left开始可以运行最多的连续机器人。这是滑动窗口的经典应用场景。
求最大充电时间（单调双向队列）
对于任意连续机器人[left,r)，如果left <= x1 < x2 < r ，且chargeTimes[x1] <= chargeTimes[x2]，则chargeTimes[x1]被 chargeTimes[x2]淘汰了。双向队列依qIndex次记录除淘汰外的x，那么qIndex对应的值是递减的，这意味者首元素对应的值就是最大值。qIndex会在以下情况被修改：
| 一 | x2淘汰x1 |
| 二 | 增加x2 |
| 三 | 移除left，left可能已经被淘汰 |
| 四 | [left,r]超过预算时：应该从队列移除r，不移除也可以，下个left会移除的。 |
注意：
r不能小于left，所以在枚举left结束时，根据需要看是否要增加r。
大致步骤
一，求前缀和。
二，枚举left。
a,枚举r。
b,更新iRet（返回值)。
c,更新双向队列。
d,如果需要更新r。
e,更新left。
枚举r退出循环
有两种情况退出循环。
| 方式一 | r=m_c,越界。[left,r)一定没超过预算，否则以方式二，退出了。 |
| 方式二 | [left,r]超出预算。[left,r)一定没超过预算，否则上一轮循环就退出了。 |
| 总结 | 两种退出方式，[left,r)都是以left开始的最长连续机器人。 |
代码
核心代码
class Solution { public: int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) { m_c = chargeTimes.size(); vector vSum = { 0 }; for (const auto& n : runningCosts) { vSum.emplace_back(n + vSum.back()); } int right = 0; std::deque qIndexs; int iRet = 0; for (int left = 0; left < m_c; left++) { //枚举r while (right < m_c) { while (qIndexs.size() && (chargeTimes[qIndexs.back()] <= chargeTimes[right])) { qIndexs.pop_back(); } qIndexs.emplace_back(right); //计算[left,right+1)的积分 const long long curCost = chargeTimes[qIndexs.front()]+(right + 1 -left)* (vSum[right+1]-vSum[left]); if (curCost > budget) { break; } right++; } iRet = max(iRet, right - left); //滑动窗口中删除left if (qIndexs.size()&&(qIndexs.front() == left)) { qIndexs.pop_front(); } if (right <= left) { right++; } } return iRet; } int m_c; };
测试用例
template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { assert(v1[i] == v2[i]); } } template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } int main() { Solution slu; vector chargeTimes, runningCosts; long long budget = 0; int res; 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; res = slu.maximumRobots(chargeTimes, runningCosts, budget); Assert(1 ,res); chargeTimes = { 3, 6, 1, 3, 4 }; runningCosts = { 2, 1, 3, 4, 5 }; budget = 25; res = slu.maximumRobots(chargeTimes, runningCosts, budget); Assert(3, res);
//CConsole::Out(res);
}
2023年3月旧代码
class Solution { public: int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) { m_c = chargeTimes.size(); int left = 0; int iRet = 0; vector vSum(1); std::deque qMaxIndexs; for (int r = 0; r < m_c; r++) { vSum.push_back(vSum.back() + runningCosts[r]); while (qMaxIndexs.size() && chargeTimes[r] >= chargeTimes[qMaxIndexs.back()]) { qMaxIndexs.pop_back(); } qMaxIndexs.push_back®; while (qMaxIndexs.size() && ((vSum[r + 1] - vSum[left])*(r - left + 1) + chargeTimes[qMaxIndexs.front()] > budget)) { if (qMaxIndexs.front() == left) { qMaxIndexs.pop_front(); } left++; } iRet = max(iRet, r - left + 1); } return iRet; } int m_c; };
2023年9月旧代码
class Solution { public: int maximumRobots(vector& chargeTimes, vector& runningCosts, long long budget) { std::deque que; int iRet = -1; long long sum = 0; for (int left = 0, r = 0; left < chargeTimes.size(); left++) { while (que.size() && (que.front() < left )) { que.pop_front(); } for (; r < chargeTimes.size(); r++) { while (que.size() && (chargeTimes[que.back()] <= chargeTimes[r])) { que.pop_back(); } que.emplace_back®; const long long curNeed = (sum+ runningCosts[r])*(r-left+1) + chargeTimes[que.front()]; if (curNeed > budget) { break; } sum += runningCosts[r]; } iRet = max(iRet, r - left ); //sum是runningCosts[left…r)的和 if (left != r) { sum -= runningCosts[left]; } else { r++; } } return iRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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
