使数组和小于等于 x 的最少时间

难度: Hard

给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：

选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。

同时给你一个整数 x 。

请你返回使 nums1 中所有元素之和 小于等于 x 所需要的最少时间，如果无法实现，那么返回 -1 。

示例 1：

输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：3
解释：
第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。

示例 2：

输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4
输出：-1
解释：不管如何操作，nums1 的和总是会超过 x 。

提示：

1 <= nums1.length <= 10³
1 <= nums1[i] <= 10³
0 <= nums2[i] <= 10³
nums1.length == nums2.length
0 <= x <= 10⁶

Submission

运行时间: 220 ms

内存: 16.3 MB

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        # 使用动态规划解决问题
        length = len(nums1)
        # 先判断0位置
        sum1 = sum(nums1)
        if sum1 <= x:
            return 0
        # 最多执行length次，那么，对nums2进行排序，从小到达，按顺序各执行1次
        # nums1会被消除，那么nums[i]就会被执行 length - i - 1次
        # 得到的thres，即为边界
        thres = sum(i*b for i,b in enumerate(sorted(nums2)[::-1]))
        if x < thres:
            return -1
        if x == thres:
            return length
        if x == thres:
            return length
        # 第一维代表对前i位进行操作
        # 第二维代表总共操作j次
        # 第0位此时就为0，不需要再做操作
        dp = [0] * (length + 1)
        
        for i, (nu2, nu1) in enumerate(sorted(zip(nums2, nums1)), 1):
            # 这里为什么是从i开始？
            # 答：因为i是前i位的意思，在遍历到i时，i以后全为0
            for j in range(i, 0, -1): 
                dp[j] = max(dp[j], dp[j - 1] + nu2 * j + nu1)
        
        sum2 = sum(nums2)
 
        for i in range(length + 1):
            # 当为0是，就是判断sum(nums1) <= x
            if sum1 + sum2 * i - dp[i]  <= x:
                    return i

        return -1

Explain

题解使用了动态规划的策略，首先预先判断nums1的初始和是否已经小于等于x，若是，则直接返回0秒。接着，考虑最多需要length次操作，对nums2进行降序排序，并计算出一个阈值thres。thres代表通过对所有元素设置为0后可以减少的最大可能值，若x小于该阈值，则直接返回-1表示无法实现。然后使用动态规划数组dp，其中dp[j]存储前i个元素操作j次能达到的最大减少值。遍历所有组合，并根据每次操作的累积结果和x的关系来判断所需的最小时间。

时间复杂度: O(n^2)

空间复杂度: O(n)

# 使用动态规划解决问题
class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        length = len(nums1)
        # 计算nums1的初始和
        sum1 = sum(nums1)
        if sum1 <= x:
            return 0  # 如果初始和已经满足条件，无需任何操作
        # 对nums2进行降序排序
        sorted_nums2 = sorted(nums2, reverse=True)
        # 计算操作后的最大可能减少值
        thres = sum(i * b for i, b in enumerate(sorted_nums2))
        if x < thres:
            return -1  # 如果x小于最大可能减少值，无法实现目标
        if x == thres:
            return length  # 如果x恰好等于thres，需要操作所有元素
        # 初始化动态规划数组
        dp = [0] * (length + 1)
        # 对nums2和nums1的元组进行排序处理
        for i, (nu2, nu1) in enumerate(sorted(zip(nums2, nums1), reverse=True), 1):
            for j in range(i, 0, -1):  # 反向遍历，确保dp[j-1]是上一轮未更新的值
                dp[j] = max(dp[j], dp[j - 1] + nu2 * j + nu1)
        # 计算总操作次数
        sum2 = sum(nums2)
        for i in range(length + 1):
            if sum1 + sum2 * i - dp[i] <= x:
                return i  # 返回满足条件的最少操作次数
        return -1  # 如果无法通过操作达到条件，返回-1

Explore

在题解中，`thres`的计算是通过排序后的`nums2`数组来实现的，计算公式为`sum(i * b for i, b in enumerate(sorted_nums2))`，这里的`i`是元素的索引，`b`是`nums2`中降序排序后的元素。此公式的本质是考虑每个元素`b`通过最大化其减少值的潜力来估计可以通过操作减少的最大总和。索引`i`代表如果操作到该元素，则它是第`i+1`个被操作的，因此它的贡献被加倍。`thres`的意义在于，它代表了在最理想的情况下（即每次操作都能达到最大单次减少量），通过操作`nums2`可以减少的最大可能总和。

如果`x`小于`thres`，这意味着即使在最理想的情况下（即每次操作都能达到最大单次减少量），通过操作`nums2`也无法达到使数组和小于等于`x`的目标。因此，如果`x`小于`thres`，则表示无论如何操作，都无法满足条件，因此直接返回`-1`表示这一不可能性。

`dp[j]`在动态规划数组中存储的是前`i`个元素操作`j`次能达到的最大减少值。在动态规划过程中，对于每个元素组合`(nu2, nu1)`，代码会反向遍历`j`从`i`到`1`，利用状态转移方程`dp[j] = max(dp[j], dp[j-1] + nu2 * j + nu1)`来更新`dp[j]`。这里`dp[j-1] + nu2 * j + nu1`考虑了如果在当前步骤将该元素设置为0，那么通过这次操作新增的减少值是多少。

对`nums2`和`nums1`的元组按降序排序的目的是为了优先处理那些具有更大潜在减少值的元素。通过这种方式，可以更快地减少总和，尽可能地在较少的操作次数内达到目标值`x`。降序排序确保了在动态规划处理过程中，每次都尝试通过最大化每个操作的影响来达到目标，这是一个策略性的决策，以提高算法的效率和可能性成功减少到目标值。