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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你两个长度相等下标从 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

请看 视频讲解 第四题。

提示 1

每个下标 i 至多操作一次。

因为操作多次的话，可以只保留最后一次，前面的操作是完全多余的（反而会让其它数字变得更大）。

所以至多操作 n 次。

试试枚举答案。

提示 2

考虑第 t 秒元素之和最小是多少。

如果从一开始到第 t 秒都不做任何操作的话，元素之和等于

s_1 + s_2\cdot t

其中 s_1 是 nums}_1 的元素和，s_2 是 nums}_2 的元素和。

考虑如何分配这 t 次操作，让数组元素分别减少多少。用 s_1 + s_2\cdot t 减去这些元素减少量之和的最大值，就是第 t 秒元素之和的最小值。

提示 3

假设已经选好了要操作的元素，那么 num}_2[i] 越大，操作的时间就应该越靠后。

例如 t=3，假设选的三个数的下标分别是 0,1,2，且 nums}_2[0]\le\textit{nums}_2[1]\le\textit{nums}_2[2]。我们可以让这些数分别减少

\textit{nums}_1[0] + \textit{nums}_2[0] \cdot x \
\textit{nums}_1[1] + \textit{nums}_2[1] \cdot y \
\textit{nums}_1[2] + \textit{nums}_2[2] \cdot z

根据 排序不等式 ，上式中的 x,y,z 应分别取 1,2,3，分别对应在第 1,2,3 秒操作，能让第 3 秒的 s_1 + s_2\cdot t 减少多少。比如 i=1 操作前是 nums}_1[1] + \textit{nums}_2[1] \cdot 3，操作后是 nums}_2[1]（因为在第 2 秒操作的，现在是第 3 秒），所以减少了 nums}_1[1] + \textit{nums}_2[1] \cdot 2。

提示 4

在第 t 秒，s_1 + s_2\cdot t 的减少量的最大值相当于求解如下问题：

按照 nums}_2[i] 从小到大排序后，从 nums}_1 中选择一个长为 t 的子序列，子序列第 j 个数的 nums}_2[i] 的系数为 j，计算减少量的最大值。

设子序列第 j 个数（j 从 1 开始）的下标为 i，那么它对减少量的贡献是

\textit{nums}_1[i] + \textit{nums}_2[i] \cdot j

由于上式中 nums}_1 并不是有序的，无法贪心，考虑用动态规划求解。

定义 f[i+1][j] 表示从前 i 个数中选出 j 个数，减少量最大是多少。

考虑第 i 个数「选或不选」：

  • 不选：f[i+1][j] = f[i][j]。
  • 选：f[i+1][j] = f[i][j-1] + \textit{nums}_1[i] + \textit{nums}_2[i] \cdot j。
  • 这两种情况取最大值，即

f[i+1][j] = max(f[i][j], f[i][j-1] + \textit{nums}_1[i] + \textit{nums}_2[i] \cdot j)

初始值 f[0][j]=0。

答案就是第一个满足

s_1 + s_2\cdot t - f[n][t] \le x

的 t。

如果不存在，则返回 -1。

代码实现时，第一个维度可以优化掉，然后像 0-1 背包 那样倒序循环 j。

[sol-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:
        n = len(nums1)
        f = [0] * (n + 1)
        for a, b in sorted(zip(nums1, nums2), key=lambda z: z[1]):
            for j in range(n, 0, -1):
                f[j] = max(f[j], f[j - 1] + a + b * j)

        s1 = sum(nums1)
        s2 = sum(nums2)
        for t, v in enumerate(f):
            if s1 + s2 * t - v <= x:
                return t
        return -1
[sol-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        int n = nums1.size(), s1 = 0, s2 = 0;
        var ps = new int[n][2];
        for (int i = 0; i < n; i++) {
            int a = nums1.get(i), b = nums2.get(i);
            s1 += a;
            s2 += b;
            ps[i] = new int[]{a, b};
        }
        Arrays.sort(ps, (a, b) -> a[1] - b[1]);

        var f = new int[n + 1];
        for (var p : ps)
            for (int j = n; j > 0; j--)
                f[j] = Math.max(f[j], f[j - 1] + p[0] + p[1] * j);

        for (int t = 0; t <= n; t++)
            if (s1 + s2 * t - f[t] <= x)
                return t;
        return -1;
    }
}
[sol-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minimumTime(vector<int> &nums1, vector<int> &nums2, int x) {
        int n = nums1.size();
        // 对下标数组排序，避免破坏 nums1 和 nums2 的对应关系
        vector<int> ids(n);
        iota(ids.begin(), ids.end(), 0);
        sort(ids.begin(), ids.end(), [&](const int i, const int j) {
            return nums2[i] < nums2[j];
        });

        vector<int> f(n + 1);
        for (int i: ids)
            for (int j = n; j; j--)
                f[j] = max(f[j], f[j - 1] + nums1[i] + nums2[i] * j);

        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        for (int t = 0; t <= n; t++)
            if (s1 + s2 * t - f[t] <= x)
                return t;
        return -1;
    }
};
[sol-Go]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func minimumTime(nums1, nums2 []int, x int) int {
	s1, s2, n := 0, 0, len(nums1)
	id := make([]int, n)
	for i := range id {
		id[i] = i
		s1 += nums1[i]
		s2 += nums2[i]
	}
	sort.Slice(id, func(i, j int) bool { return nums2[id[i]] < nums2[id[j]] })

	f := make([]int, n+1)
	for _, i := range id {
		for j := n; j > 0; j-- {
			f[j] = max(f[j], f[j-1]+nums1[i]+nums2[i]*j)
		}
	}

	for t, v := range f {
		if s1+s2*t-v <= x {
			return t
		}
	}
	return -1
}

func max(a, b int) int { if b > a { return b }; return a }
[sol-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
var minimumTime = function(nums1, nums2, x) {
    const n = nums1.length;
    let f = Array(n + 1).fill(0);
    for (const [a, b] of _.zip(nums1, nums2).sort((a, b) => a[1] - b[1]))
        for (let j = n; j; j--)
            f[j] = Math.max(f[j], f[j - 1] + a + b * j);

    const s1 = _.sum(nums1);
    const s2 = _.sum(nums2);
    for (let t = 0; t <= n; t++)
        if (s1 + s2 * t - f[t] <= x)
            return t;
    return -1;
};

复杂度分析

  • 时间复杂度：\mathcal{O}(n^2)，其中 n 为 nums}_1 的长度。
  • 空间复杂度：\mathcal{O}(n)。
 Comments
On this page
2809-使数组和小于等于 x 的最少时间
  1. 提示 1
  2. 提示 2
  3. 提示 3
  4. 提示 4