2809：使数组和小于等于 x 的最少时间（2978 分）

力扣第 110 场双周赛第 4 题

题目

给你两个长度相等下标从 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 <= 103
• 1 <= nums1[i] <= 103
• 0 <= nums2[i] <= 103
• nums1.length == nums2.length
• 0 <= x <= 106

分析

• 首先，每个下标最多操作一次（否则第一次多余）
• 假设不操作，令 s1=sum(nums1),s2=sum(nums2)，第 i 秒的和为 s1+s2 * i
• 如果要操作的 i 个下标依次是 a1,a2,…,ai，减少的即是 f(i)=sum(nums[a1]+nums2[a1]*i)
• 根据排序不等式，nums2[ai] 应该递增，f(i) 才会最大
• 因此，将下标按 nums2 排序，dp 即可求出 f(i)
• 枚举 i，判断是否 s1+s2 * i-f(i)<=x 即可

解答

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

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        A = sorted(zip(nums2,nums1))
        n = len(A)
        f = [0]*(n+1)
        for a,b in A:
            for i in range(n,0,-1):
                f[i] = max(f[i],f[i-1]+a*i+b)
        s1,s2 = sum(nums1),sum(nums2)
        for i in range(n+1):
            if s1+s2*i-f[i]<=x:
                return i    
        return -1

1094 ms