Leetcode 第 110 场双周赛 Problem D 2809. 使数组和小于等于 x 的最少时间（DP+贪心+正难则反）

• Leetcode 第 110 场双周赛 Problem D 2809. 使数组和小于等于 x 的最少时间（DP 好题）
• 题目
  • 给你两个长度相等下标从 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.length <= 10 ^ 3
  • 1 <= nums1[i] <= 10 ^ 3
  • 0 <= nums2[i] <= 10 ^ 3
  • nums1.length == nums2.length
  • 0 <= x <= 10 ^ 6
• 解法
  • DP+贪心+正难则反：
  • 第 1 步：
  • 每个 nums1[i] 置为 0，超过一次不如仅最后一次置为 0，
  • 可知对于 nums1[i] 一样大，且不会影响其他 nums1，
  • 因此时间最多就是 nums1.len、超过则无意义，
  • 第 2 步：
  • 问题转化为经过最少 s 秒且 s <= nums1.len，使得 nums3 = nums2[x]*(s-1) + nums2[y]*(s-2) + … + nums2[z]*0 + nums1[a] + …，nums3.len = nums1.len
  • nums3 总和 sum(nums3) 小于等于 x 时，最小的 s 就是答案，否则答案就是 -1，
  • 同时不可能推出 s 单调性，因此无法二分答案，
  • 第 3 步：
  • 正面直接求最小值无法想到什么贪心策略，如果使用 DP 则第 j+1 秒会影响前 j 秒的数据，因为每秒每个元素会加上 nums2，不满足无后效性，
  • 正难则反：
    • 求经过 s 秒最多可以减少多少
    • 总数 sum(nums1) + s*sum(nums2) 减去即可
  • 第 4 步：
  • 动规状态：dp[i][j] 为前 i 个数经过 j 秒最多可以减少多少，注意 i>=j，
  • 初始化 dp[i][0]=0，即前 i 个数不经过任何时间则无法减少
  • 第 5 步：
  • 转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-1] + nums1[i-1]+j*nums2[i-1])，
    • 即第 i 个数经过 j 秒是否删除的最大值，取决于是否需要再第 j 秒清理掉第 i 个元素
    • 此时 DP 无后效性，因为第 i+1 个数不会影响前 i 个数的更新，
    • 同时需要满足减少 j 个元素的最大值、等于减少前（i-1 个元素中选 j-1 个元素）的最大值加第 i 个元素，
    • 可以观察减少的是 nums1[i-1]+j*nums2[i-1]，由于前 j 秒等价于选 j 个元素，此时 nums1 顺序无所谓，j 固定升序、保证 j*nums2[i-1] 最大需要使 nums2 升序（nums1 跟随排序）
  • 第 6 步：
  • 最后结果就是枚举秒数 j=[0,nums1.len]，sum(nums1) + j * sum(nums2) - dp[nums1.len][j] <= x，找到最小的 j，没有则返回 -1
  • 空间压缩：由于 dp[i][j] 仅与 dp[i-1][j]、dp[i-1][j-1] 有关，因此可以使用一维 dp[j] 倒序处理
  • 时间复杂度：O(n ^ 2)，空间复杂度：O（n）
• 代码

/*** DP+贪心+正难则反：** 第 1 步：* 每个 nums1[i] 置为 0，超过一次不如仅最后一次置为 0，* 可知对于 nums1[i] 一样大，且不会影响其他 nums1，* 因此时间最多就是 nums1.len、超过则无意义，** 第 2 步：* 问题转化为经过最少 s 秒且 s <= nums1.len，使得 nums3 = nums2[x]*(s-1) + nums2[y]*(s-2) + ... + nums2[z]*0 + nums1[a] + ...，nums3.len = nums1.len* nums3 总和 sum(nums3) 小于等于 x 时，最小的 s 就是答案，否则答案就是 -1，* 同时不可能推出 s 单调性，因此无法二分答案，** 第 3 步：* 正面直接求最小值无法想到什么贪心策略，如果使用 DP 则第 j+1 秒会影响前 j 秒的数据，因为每秒每个元素会加上 nums2，**不满足无后效性**，* 正难则反：*     * 求经过 s 秒最多可以减少多少*     * 总数 sum(nums1) + s*sum(nums2) 减去即可** 第 4 步：* 动规状态：dp[i][j] 为前 i 个数经过 j 秒最多可以减少多少，注意 i>=j，* 初始化 dp[i][0]=0，即前 i 个数不经过任何时间则无法减少** **第 5 步**：* 转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-1] + nums1[i-1]+j*nums2[i-1])，*     * 即第 i 个数经过 j 秒是否删除的最大值，取决于是否需要再第 j 秒清理掉第 i 个元素*     * **此时 DP 无后效性**，因为第 i+1 个数不会影响前 i 个数的更新，*     * 同时需要满足减少 j 个元素的最大值、等于减少前（i-1 个元素中选 j-1 个元素）的最大值加第 i 个元素，*     * 可以观察减少的是 nums1[i-1]+j*nums2[i-1]，由于前 j 秒等价于选 j 个元素，此时 nums1 顺序无所谓，**j 固定升序、保证 j*nums2[i-1] 最大需要使 nums2 升序（nums1 跟随排序）**** 第 6 步：* 最后结果就是枚举秒数 j=[0,nums1.len]，sum(nums1) + j * sum(nums2) - dp[nums1.len][j] <= x，找到最小的 j，没有则返回 -1* 空间压缩：由于 dp[i][j] 仅与 dp[i-1][j]、dp[i-1][j-1] 有关，因此可以使用一维 dp[j] 倒序处理* 时间复杂度：O(n ^ 2)，空间复杂度：O（n）*/public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) {// 判空与异常if (nums1 == null || nums2 == null || nums1.size() != nums2.size() || nums1.size() <= 0) {return -1;}int n = nums1.size();// 求总和int sumNums1 = nums1.stream().mapToInt(Integer::intValue).sum();int sumNums2 = nums2.stream().mapToInt(Integer::intValue).sum();
//        System.out.println(sumNums1);
//        System.out.println(sumNums2);// j 固定升序、保证 j*nums2[i-1] 最大需要使 nums2 升序（nums1 跟随排序）List<Pair<Integer, Integer>> numsPair = new ArrayList<>(n);for (int i = 0; i < n; i++) {numsPair.add(new Pair<>(nums2.get(i), nums1.get(i)));}Collections.sort(numsPair, (o1, o2) -> o1.getKey() - o2.getKey());
//        System.out.println(numsPair);// 动规状态：dp[i][j] 为前 i 个数经过 j 秒最多可以减少多少，注意 i>=j，初始化 dp[i][0]=0，即前 i 个数不经过任何时间则无法减少，空间压缩掉 iint[] dp = new int[n + 1];// 转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-1] + nums1[i-1]+j*nums2[i-1])，for (int i = 1; i < n + 1; i++) {// 空间压缩，一维 dp[j] 倒序处理for (int j = i; j >=1; j--) {dp[j] = Math.max(dp[j], dp[j-1] + numsPair.get(i-1).getValue() + j * numsPair.get(i-1).getKey());}}
//        AlgorithmUtils.systemOutArray(dp);int res = -1;// 枚举秒数 j=[0,nums1.len]，sum(nums1) + j * sum(nums2) - dp[nums1.len][j] <= x，找到最小的 j，没有则返回 -1for (int j = 0; j <= n; j++) {if (sumNums1 + j * sumNums2 - dp[j] <= x) {res = j;break;}}return res;}