6143. 预算内的最多机器人数目--（每日一难phase2--day7）

6143. 预算内的最多机器人数目

你有 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] <= 1e5
1 <= budget <= 1e15

解析：

• 看到连续，开销不超过，最大个数等要求，就要联想到滑动窗口，滑动窗口题目就是以这样的形式出现（两个指针（first，second）分别指向窗口开头、末尾）。
• 使用开销来判断指针的移动，如果开销小于budget，second右移，如果开销大于budget，first右移。
• 开销的第一项为区间内的最大值，窗口移动区间内的最大值也会变化。可以使用双端队列（单调递减，同时记录下标）维护最大值（队列尾部存放最大值，取最大值时如果头部元素下标小于first就将头部弹出）
• 例如：3 6 1 3 4
• 加入3 ；
• 加入6，3<6将3弹出，剩下6；
• 加入1，剩下6 1；
• 加入3，弹出1，剩下6 3
• 加入4，弹出3，剩下6 3
• 每次取最大元素，从队尾取，如果6 的下标
• 还可以使用priority_queue> 懒删除，只需要在寻找最大值时看一下最大值下标是否小于first即可，不符合直接移除。
• sum(2,1,3)，可以使用前缀和求解，知道first，second前缀和直接就能计算。

代码：

class Solution {
public:
    // 前缀和+滑动窗口
    int maximumRobots(vector<int>& ch, vector<int>& ru, long long bu) {
        int n=ch.size();
        long long sum[n+1];
        memset(sum,0,sizeof(sum));
        // 前缀和（0号元素不用，方便处理）
        for(int i=1;i<=n;i++){
            sum[i]+=ru[i-1]+sum[i-1];
        }   
        // 左指针，右指针
        int first=0,second=0,res=0;
        long long cost=0;
        // 存放最大值
        priority_queue<pair<int,int>> q;
        while(second<n){
        	// 将second加到窗口内
            q.emplace(ch[second],second);
            // 计算花费
            cost=q.top().first+(second-first+1)*(sum[second+1]-sum[first]);
            // 不符合就移动左指针
            while(first<=second&&cost>bu){
                ++first;
                // 如果堆顶元素下标小于first说明需要淘汰了
                while(!q.empty()&&q.top().second<first){
                    q.pop(); 
                }
                // 淘汰最左侧之后计算花费
                cost=q.top().first+(second-first+1)*(sum[second+1]-sum[first]);
            }
            // 符合条件之后的窗口大小
            res=max(res,second-first+1);
            // 移动右指针，继续运行
            second++;
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39