好久没有写博客了，来水一篇吧。

题目

——预算内最多机器人数量

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

思路

题目大意，有一队机器人，每个机器人有各自的chargeTime和runningCost，求最长连续机器人数组长度，使得max(chargeTime)+k*sum(runningCost)不大于budget。

首先看下数据范围，n<=5*10⁴，根据经验，时间复杂度一定要控制在O(n²)以下。

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

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

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

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

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

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

代码

这里直接贴代码，时间复杂度O(nlog(n))，空间复杂度O(n)。

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[0][0] <= budget:
                return True
            for i in range(n, len(chargeTimes)):
                while len(hp) > 0 and hp[0][1] <= i - n:
                    heapq.heappop(hp)
                heapq.heappush(hp, (-chargeTimes[i], i))
                sm += runningCosts[i] - runningCosts[i - n]
                if n * sm - hp[0][0] <= 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

看起来没啥人提交的样子，AC，收工！

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

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/09/04/leetcdoe-2398-maximum-number-of-robots-within-budget/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！