每日一题

题目

预算内的最多机器人数目
你有 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 。

通过代码

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
class Solution {
public:
	int maximumRobots(vector<int>& chargeTimes, vector<int>& runningCosts, long long budget) {
		int n = runningCosts.size();
		vector<long long> rs = vector<long long>(n+1); // 初始前缀和
		for(int i=0;i<n;i++){
			rs[i+1] = rs[i] + runningCosts[i];
		}
		int l=0, r=0; // 初始滑动窗口
		long long testBudget=0;
		priority_queue<int> q; //滑动窗口维护的优先队列
		while(r<n){
			if(chargeTimes[r] > q.top()){  //判断新加元素是否大于队列中最大元素
                // 清空队列
				while(!q.empty()){
					q.pop();
				}
			}
			q.push(chargeTimes[r]);		
			r++;
			testBudget = (long long)q.top() + (r-l)*(rs[r]-rs[l]);
			if(budget < testBudget){ // 不符要求，整体右移
				if(chargeTimes[l]==q.top()){  // 判断左端出队元素是否为最大元素
					q.pop();
				}
				l++;
			}
		}
		return r-l;
	}
};

代码解释

看到题目描述中的 连续 我就想到了 前缀和。
又在子序列最大联想到 滑动窗口 。
本文题目并不是固定长度的滑动窗口，但是求最长所以长度，所以只增不减
右端一直是入队的，判断是否符合要求。若不符合，左端出队（相当于整体右移）
最后返回滑动窗口长度