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

(Updated: )
(3 mins to read)

题意

给定长度为$n$的数组nums1和nums2，在每一秒，每个nums1[i]会增加nums2[i]，然后你可以选择一个数将其置0，问你使nums1中所有数的和小于等于$x$的最少用时。

$1\le n \le 1000, 1\le nums1[i] \le 1000, 0\le nums2[i] \le 1000, 0\le x \le 10^6$

做法

每日一题没做出来😭。

显然对一个位置$i$至多只会操作1次，因为如果操作多次，那么除了最后一次，前几次都是没有意义的，还不如用来操作别的位置。因此用时上限是$n$，否则就是永远不行（-1）。

如果固定操作的$t$个位置，显然应该按照nums2从小到大置0的收益是最大的。

现在的问题就是这$t$个位置怎么选？这一步我没想出来，一直在想贪心的方法，当时脑子也晕晕的🤡。

考虑将所有数按照nums2从小到大排序，那么第$i$个选择的数$j$就应该在第$i$天操作，它能带来的贡献就是省下$nums1[j] + i * nums2[j]$。想到这里应该很容易想到$dp[i][j]$表示考虑了前$i$个数，选择了$j$个能带来的最大贡献。然后就做完了。。。$O(n^2)$

代码都不是我自己写的，偷懒CV的

notes：rust写算法题优先选用sort_unstable。这个DP就是个01背包，所以可以省掉第一维，然后倒序DP。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
impl Solution {
    pub fn minimum_time(nums1: Vec<i32>, nums2: Vec<i32>, x: i32) -> i32 {
        let mut pairs = nums1.iter().zip(nums2.iter()).collect::<Vec<_>>();
        pairs.sort_unstable_by(|a, b| a.1.cmp(b.1));

        let n = pairs.len();
        let mut f = vec![0; n + 1];
        for (i, (a, b)) in pairs.into_iter().enumerate() {
            for j in (1..=(i + 1)).rev() {
                f[j] = f[j].max(f[j - 1] + a + b * j as i32);
            }
        }

        let s1 = nums1.iter().sum::<i32>();
        let s2 = nums2.iter().sum::<i32>();
        for (t, v) in f.iter().enumerate() {
            if s1 + s2 * t as i32 - v <= x {
                return t as i32;
            }
        }
        -1
    }
}