Basic knowledge points involved in this article
C++ algorithm: principles, source code and test cases of prefix sum, prefix product, prefix XOR including course videos
Monotone bidirectional queue
sliding window
Title
You have n robots and are given two integer arrays with indexes starting from 0, chargeTimes and runningCosts, both of length n. The charging time of the i-th robot is chargeTimes[i] unit time, and it takes runningCosts[i] unit time to run. Give you another integer budget .
The total cost of running k robots is max(chargeTimes) + k * sum(runningCosts), where max(chargeTimes) is the maximum charging time among the k robots, and sum(runningCosts) is the sum of the running times of the k robots.
Please return the maximum number of robots that you can run continuously without exceeding the budget.
Example 1:
Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
Output: 3
explain:
It is possible to run all single robots within budget or run 2 robots consecutively.
Selecting the first 3 robots will give you a maximum answer of 3. The total overhead is max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 , which is less than 25 .
We can see that we can’t run more than 3 robots continuously within the budget, so we return 3 .
Example 2:
Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
Output: 0
Explanation: Even running any single robot will still exceed the budget, so we return 0 .
Parameter range:
chargeTimes.length == runningCosts.length == n
1 <= n <= 5 * 104
1 <= chargeTimes[i], runningCosts[i] <= 105
1 <= budget <= 1015
Analysis
Time complexity
Two levels of looping, but the second level of looping does not start from scratch. So the total time complexity is O(n).
Sliding window
[left,r) If r increases, the budget also increases. For each left, we find the first r that makes [left, r] exceed the budget, that is, [left, r) can run the most continuous robots starting from left. This is a classic application scenario of sliding windows.
Find the maximum charging time (monotonic two-way queue)
For any continuous robot [left,r), if left <= x1 < x2 < r, and chargeTimes[x1] <= chargeTimes[x2], then chargeTimes[x1] is eliminated by chargeTimes[x2]. The two-way queue records x except elimination by qIndex times, then the value corresponding to qIndex is decreasing, which means that the value corresponding to the first element is the maximum value. qIndex will be modified in the following situations:
| One | x2 eliminated x1 |
| two | increase x2 |
| three | remove left , left may have been eliminated |
| four | [left,r] exceeds the budget: r should be removed from the queue, or not removed. The left will be removed next time. |
Note:
r cannot be less than left, so at the end of enumerating left, see if you want to increase r as needed.
General steps
1. Find the sum of prefixes.
Second, enumerate left.
a, enumeration r.
b. Update iRet (return value).
c. Update the bidirectional queue.
d, if necessary update r.
e, update left.
Enumeration r exits the loop
There are two situations to exit the loop.
| Method 1 | r =m_c, out of bounds. [left,r) must not have exceeded the budget, otherwise we will exit in the second way. |
| Method 2 | [left,r] exceeds the budget. [left,r) must not have exceeded the budget, otherwise the last cycle would have exited. |
| Summary | The two exit methods, [left, r) are both the longest continuous robots starting with left. |
Code
Core code
class Solution {
public:
int maximumRobots(vector & amp; chargeTimes, vector & amp; 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 + + )
{
//enumeration r
while (right < m_c)
{
while (qIndexs.size() & amp; & amp; (chargeTimes[qIndexs.back()] <= chargeTimes[right]))
{
qIndexs.pop_back();
}
qIndexs.emplace_back(right);
//Calculate the integral of [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);
//Delete left in sliding window
if (qIndexs.size() & amp; & amp;(qIndexs.front() == left))
{
qIndexs.pop_front();
}
if (right <= left)
{
right + + ;
}
}
return iRet;
}
int m_c;
};
Test cases
template
void Assert(const vector & amp; v1, const vector & amp; 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 slug;
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);
}
Old code in March 2023
class Solution {
public:
int maximumRobots(vector & amp; chargeTimes, vector & amp; 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() & amp; & amp; chargeTimes[r] >= chargeTimes[qMaxIndexs.back()])
{
qMaxIndexs.pop_back();
}
qMaxIndexs.push_back?;
while (qMaxIndexs.size() & amp; & amp; ((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;
};
Old code in September 2023
class Solution {
public:
int maximumRobots(vector & amp; chargeTimes, vector & amp; 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() & amp; & amp; (que.front() < left ))
{
que.pop_front();
}
for (; r < chargeTimes.size(); r + + )
{
while (que.size() & amp; & amp; (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 is the sum of runningCosts[left…r)
if (left != r)
{
sum -= runningCosts[left];
}
else
{
r + + ;
}
}
return iRet;
}
};
Extended reading
Video course
Effective learning: clear goals, timely feedback, stretching zone (appropriate difficulty), you can learn simple courses first, please go to CSDN Academy and listen to the explanation of Baiyin Lecturer (that is, I).
https://edu.csdn.net/course/detail/38771
how fast do you want
A battle has quickly formed. To share the worries of your boss, please learn C# onboarding training, C++ onboarding training and other courses.
https://edu.csdn.net/lecturer/6176
Related downloads
If you want to know the superior learning algorithm, please download the doc version of “Algorithm Book When You Hear the Defects”
https://download.csdn.net/download/he_zhidan/88348653
| What I want to say to you all
|
|-|
|Rejoicing when you hear defects is a good wish, to find problems early, correct them early, and save money for the boss. |
| The origin of the Mohist name: Everything is recorded in Mohism. |
|If the program is a dragon, then the algorithm is his key point|
Test environment
Operating system: win7 Development environment: VS2019 C++ 17
Or operating system: win10 development environment:
VS2022 C++ 17
