2398. 预算内的最多机器人数目（24.9.13）

题目

有n个机器人，给定两个下标从 0 开始的整数数组chargeTimes和runningCosts，两者长度都为(n)。第(i)个机器人充电时间为chargeTimes[i]单位时间，花费runningCosts[i]单位时间运行。另外还有一个整数budget。

运行(k)个机器人总开销是max(chargeTimes) + k * sum(runningCosts)，其中(\text{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。总开销是(\text{max(3,6,1)}+3\times\text{sum(2,1,3)} = 6 + 3\times6 = 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 * 10^4
• 1 <= chargeTimes[i], runningCosts[i] <= 10^5
• 1 <= budget <= 10^15

解题思路

见代码

代码

class Solution {
public:
    int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
        int n=chargeTimes.size();
        int ans=0;
        long long sum=0;//用于记录sum(runningCosts)
        int l;
        deque<int> q;//利用双端队列来 保持max(chargeTimes)
        for(int r=0;r<n;r++){
            //入
            while(!q.empty()&&chargeTimes[q.back()]<=chargeTimes[r]){
                q.pop_back();
            }
            q.push_back(r);
            sum+=runningCosts[r];
            //出
            while(!q.empty()&&chargeTimes[q.front()]+(r-l+1)*sum>budget){
                if(q.front()==l){
                    //当其等于滑动窗口的左端点时说明将会滑出窗口
                    q.pop_front();
                }
                sum-=runningCosts[l++];
                //更新窗口,将左端点想右方移动，用于减少
                //用来保持 chargeTimes[q.front()]+(r-l+1)*sum <= budget
            }
            //更新答案
            ans=max(ans,r-l+1);
        }
        return ans;
    }
};