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⁶

解题思路

这是一个复杂的动态规划问题，需要仔细分析操作的最优策略。

核心观察：

  1. 每个位置最多操作一次：如果对同一个位置操作多次，我们可以只保留最后一次操作，因为前面的操作都是浪费的。

  2. 操作顺序很重要：应该按照 nums2[i] 的值从小到大进行操作。原因是增长率越大的位置，我们应该越晚清零，这样能节省更多的增长量。

  3. 状态设计：设 dp[i][j] 表示在前 i 个元素中进行 j 次操作所能减少的最大总和。

算法步骤：

  1. 首先将所有位置按照 nums2[i] 的值排序
  2. 使用动态规划计算每种操作次数下的最大减少量
  3. 对于每个可能的时间 t，检查是否满足条件：初始和 + 增长量*t - 最大减少量 ≤ x

状态转移方程：

  • dp[i][0] = 0（不进行操作）
  • dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + nums2[i-1] * j + nums1[i-1])

第二项表示选择第 i-1 个位置作为第 j 次操作，减少的总量为该位置的初始值加上它在前 j-1 秒的增长量。

代码实现

class Solution {
public:
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
        int n = nums1.size();
        vector<pair<int, int>> pairs;
        
        for (int i = 0; i < n; i++) {
            pairs.push_back({nums2[i], nums1[i]});
        }
        sort(pairs.begin(), pairs.end());
        
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i][j] = max(dp[i-1][j], 
                              dp[i-1][j-1] + pairs[i-1].first * j + pairs[i-1].second);
            }
        }
        
        int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
        int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
        
        for (int t = 0; t <= n; t++) {
            if (sum1 + sum2 * t - dp[n][t] <= x) {
                return t;
            }
        }
        
        return -1;
    }
};

class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1)
        pairs = sorted(zip(nums2, nums1))
        
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        
        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i][j] = max(dp[i-1][j], 
                              dp[i-1][j-1] + pairs[i-1][0] * j + pairs[i-1][1])
        
        sum1 = sum(nums1)
        sum2 = sum(nums2)
        
        for t in range(n + 1):
            if sum1 + sum2 * t - dp[n][t] <= x:
                return t
        
        return -1

public class Solution {
    public int MinimumTime(IList<int> nums1, IList<int> nums2, int x) {
        int n = nums1.Count;
        var pairs = new List<(int, int)>();
        
        for (int i = 0; i < n; i++) {
            pairs.Add((nums2[i], nums1[i]));
        }
        pairs.Sort();
        
        int[,] dp = new int[n + 1, n + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i, j] = Math.Max(dp[i-1, j], 
                                   dp[i-1, j-1] + pairs[i-1].Item1 * j + pairs[i-1].Item2);
            }
        }
        
        int sum1 = nums1.Sum();
        int sum2 = nums2.Sum();
        
        for (int t = 0; t <= n; t++) {
            if (sum1 + sum2 * t - dp[n, t] <= x) {
                return t;
            }
        }
        
        return -1;
    }
}

var minimumTime = function(nums1, nums2, x) {
    const n = nums1.length;
    const pairs = [];
    
    for (let i = 0; i < n; i++) {
        pairs.push([nums2[i], nums1[i]]);
    }
    pairs.sort((a, b) => a[0] - b[0]);
    
    const dp = Array(n + 1).fill(null).map(() => Array(n + 1).fill(0));
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j <= i; j++) {
            dp[i][j] = Math.max(dp[i-1][j], 
                               dp[i-1][j-1] + pairs[i-1][0] * j + pairs[i-1][1]);
        }
    }
    
    const sum1 = nums1.reduce((a, b) => a + b, 0);
    const sum2 = nums2.reduce((a, b) => a + b, 0);
    
    for (let t = 0; t <= n; t++) {
        if (sum1 + sum2 * t - dp[n][t] <= x) {
            return t;
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n²)
空间复杂度O(n²)

其中 n 是数组长度。时间复杂度主要来自于排序 O(n log n) 和动态规划 O(n²)，空间复杂度来自于 dp 数组。