# 2398. Maximum Number of Robots Within Budget

## 题目

You have `n` robots. You are given two 0-indexed integer arrays, `chargeTimes` and `runningCosts`, both of length `n`. The `ith` robot costs `chargeTimes[i]` units to charge and costs `runningCosts[i]` units to run. You are also given an integer `budget`.

The total cost of running `k` chosen robots is equal to `max(chargeTimes) + k * sum(runningCosts)`, where `max(chargeTimes)` is the largest charge cost among the `k` robots and `sum(runningCosts)` is the sum of running costs among the `k` robots.

Return the maximum number of consecutive robots you can run such that the total cost does not exceed `budget`.

Example 1:

```Input: chargeTimes = [3,6,1,3,4], runningCosts = [2,1,3,4,5], budget = 25
Output: 3
Explanation:
It is possible to run all individual and consecutive pairs of robots within budget.
To obtain answer 3, consider the first 3 robots. The total cost will be max(3,6,1) + 3 * sum(2,1,3) = 6 + 3 * 6 = 24 which is less than 25.
It can be shown that it is not possible to run more than 3 consecutive robots within budget, so we return 3.
```

Example 2:

```Input: chargeTimes = [11,12,19], runningCosts = [10,8,7], budget = 19
Output: 0
Explanation: No robot can be run that does not exceed the budget, so we return 0.
```

Constraints:

• `chargeTimes.length == runningCosts.length == n`
• `1 <= n <= 5 * 104`
• `1 <= chargeTimes[i], runningCosts[i] <= 105`
• `1 <= budget <= 1015`

## 思路

hint给的思路给的很详细，直接按这个展开下。（其实是我自己没想出来别的思路，囧）

1.二分查找，确定最长的连续序列长度

2.二分查找子问题，给定子数组长度n，求是否存在连续子数组，满足给定条件

3对于n，使用滑动窗口遍历所有长度n的子数组，求是否满足max(chargeTime)+k*sum(runningCost)<=budget

——如何求子数组的最大值？有两种思路，一种是使用BIT，一种是使用堆/OrderedSet。

——这里需要注意的是，如果使用heapq，需要使用lazy delete，否则很容易超时。

## 代码

``````import heapq
class Solution(object):

def maximumRobots(self, chargeTimes, runningCosts, budget):
"""
:type chargeTimes: List[int]
:type runningCosts: List[int]
:type budget: int
:rtype: int
"""

def valid(n):
hp = [(-chargeTimes[i], i) for i in range(n)]
heapq.heapify(hp)
sm = sum(runningCosts[:n])
if n * sm - hp <= budget:
return True
for i in range(n, len(chargeTimes)):
while len(hp) > 0 and hp <= i - n:
heapq.heappop(hp)
heapq.heappush(hp, (-chargeTimes[i], i))
sm += runningCosts[i] - runningCosts[i - n]
if n * sm - hp <= budget:
return True

return False

l, r = 1, len(chargeTimes) + 1
while l < r:
mid = l + (r - l) // 2
if valid(mid):
l = mid + 1
else:
r = mid
return l - 1``````

——此处是内容的分割线——