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

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

Related Topics

  • 数组
  • 动态规划
  • 排序

题目链接: link

解答

今天的题目好难啊，难度为 Hard, 我没有做出来，但是还是可以根据题目已有信息尝试分析一下。

首先就是对于每个位置，我们最多操作一次，为什么呢？因为如果我们对同一个位置操作多次的话，完全可以只保留最后一次，这样还能避免其他位置的数字多次增加，反而导致整体更大。

其次，假定我们已经确定了我们要操作的位置，比如 i_1,i_2,i_3,...,i_k, 那我们操作的顺序应当从 nums2[i_j] 中小的开始，因为如果我们先从 nums2[i_j] 大的位置开始的话，之后我们就不会操作这个位置了，那么这个位置就会增加的值次数就会更多，因为我们没有假定 i_1<=i_2<=i_3<=...<=i_k, 因此我们可以假定 nums2[i_1] <= nums2[i_2]<=...<=nums2[i_k], 毕竟总能排成这样的，根据顺序再决定 i_j 的值就好了。

我们假设 nums2[n] <= nums[m], 并且 nums2[n] 与 nums2[m] 之间间隔了 l 个选定的位置那我们会发现 先进行操作位置 n 再操作位置 m和 先操作位置 m 再操作位置 n,对于前者位置 n 的值为 (l+1) * num2s[n] 而位置 m 的值为 0, 对于后者位置 n 的值为 0 而位置 m 的值为 (l+1) * nums2[m], 此时其他位置的值是相同的, 因此整体的值是前者更小。

因此对于任意两个位置的操作顺序我们都可以进行调换，调换到位置对应的值小的先进行操作。

我们假设 nums1 的和为 s1, nums2 的和为 s2, 那么对于操作 t 次后, 我们的值就为 s1 + s2*t 并减去减少量的值, 我们就需要考虑对于不同的 t 能够最多减少多少。

以上就是我能够考虑到的部分。接下来的是看解析的。

假设我们对于位置 i 在第 r 次进行操作, 那么到了第 k 次, 此时 nums1[i] 的值为 (k-r)*nums[i], 对于整体减少的值为 nums1[i]+r*nums2[i], 我们不妨假设 k=3, 并且操作的3个位置分别为 3,6,9, 那么 3 次操作后对整体减少的值为 nums1[3]+r1*nums2[3]+nums1[6]+r2*nums2[6]+nums1[9]+r3*nums2[9], 因为我们希望整体减少的最多的前提是我们现在已经确认了就选择 3,6,9 这三个位置, 在确认位置的前提下对操作顺序进行排序, 达到整体减少最多, 因此问题转为求 r1*nums2[3]+r2*nums2[6]+r3*nums2[9] 的最大值, 我们不妨假设 nums2[3] <= nums2[6] <= nums2[9], 那么由排序不等式可知, 当 r1<=r2<=r3 时, r1*nums2[3]+r2*nums2[6]+r3*nums2[9] 最大.

由于输出与位置无关, 因此为了方便我们可以将 nums2 进行排序, 当然需要将 nums1 与 nums2 绑在一起，根据 nums2 的值进行排序.

由于场景的特殊性, 因此此时 r 的取值与排序相同, 例如上面例子取到最大的值时为 r1=1,r2=2,r3=3.

定义 f[i+1][j] 表示从 0,1,2,...,i 中选 j 个下标（j<=i+1）, 减少量最大的值, 那么我们考虑下标 i:

  • 不选 i， 问题变成从 0,1,2,...,i-1 中选 j 个下标, 减少量最大值是多少, 即 f[i+1][j] = f[i][j]
  • 如果选 i, 问题变成从 0,1,2,...,i-1 中选 j-1 个下标, 减少量最大值是多少, 即 f[i+1][j] = f[i][j-1] + nums1[i] + nums2[i] * j

最后最大值就是两种情况的最大值,

f[i+1][j] = max(f[i][j], f[i][j-1] + nums1[i] + nums2[i] * j)

初始值很自然就是 0 个点中选 0个, 那自然 f[0][0]=0, 答案为第一个满足 s1+s2*t-f[n][t]<=x 的 t, 如果不存在, 则返回 -1.

class Solution {
    public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {
        // 计算 nums1 的总和 s1 , nums2 的总和 s2
        int n = nums1.size(), s1 = 0, s2 = 0;
        // 定义的 f[i+1][j]
        int[][] dp = new int[n + 1][n + 1];
        // 把两个放在一起, 一起排序
        List<List<Integer>> nums = new ArrayList<>();
        // 这里作者把 nums1 和 nums2 换了顺序
        for (int i = 0; i < n; i++) {
            int a = nums1.get(i), b = nums2.get(i);
            nums.add(Arrays.asList(b, a));
            s1 += a;
            s2 += b;
        }
        // 排序
        Collections.sort(nums, (o1, o2) -> Integer.compare(o1.get(0), o2.get(0)));
        // 从 j=1 即最多1个节点开始
        // 他这个和他写的解析有点反，应该把 j换成i，i换成j好一点.
        for (int j = 1; j <= n; ++j) {
            int b = nums.get(j - 1).get(0), a = nums.get(j - 1).get(1);
            for (int i = j; i > 0; --i) {
                dp[j][i] = Math.max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);
            }
        }
        // 然后这里就看 t 什么时候 OK
        for (int i = 0; i <= n; i++) {
            if (s2 * i + s1 - dp[n][i] <= x) {
                return i;
            }
        }
        return -1;
    }
}

感觉这种题目常常都是考虑很小的情况开始, 然后慢慢从 2 个推广到 n 个。下次多写写.