2398：预算内的最多机器人数目（1917 分）

力扣第 86 场双周赛第 4 题

题目

你有 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] <= 105
• 1 <= budget <= 1015

相似问题：

• 0239：滑动窗口最大值
• 2040：两个有序数组的第 K 小乘积（2517 分）
• 2071：你可以安排的最多任务数目（2648 分）
• 2064：分配给商店的最多商品的最小值（1885 分）
• 2187：完成旅途的最少时间（1640 分）

分析

典型的滑动窗口，维护窗口不超过 budget 即可。

其中，维护 chargeTimes 的窗口最大值即是问题 0239

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

def maximumRobots(self, chargeTimes: List[int], runningCosts: List[int], budget: int) -> int:
	Q, s = deque(), 0
	res, i = 0, 0
	for j,(t,c) in enumerate(zip(chargeTimes, runningCosts)):
		while Q and Q[-1][-1]<=t:
			Q.pop()
		Q.append((j, t))
		s += runningCosts[j]
		while Q and Q[0][-1]+(j-i+1)*s>budget:
			if Q[0][0]==i:
				Q.popleft()
			s -= runningCosts[i]
			i += 1
		res = max(res, j-i+1)
	return res

360 ms