C++前缀和算法的应用：预算内的最多机器人数目

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);

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;
};

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;
}
};