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

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.length <= 10^3
• 1 <= nums1[i] <= 10^3
• 0 <= nums2[i] <= 10^3
• nums1.length == nums2.length
• 0 <= x <= 10^6

示例 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 。

分析

• 首先要让总和尽可能小，那么肯定是优先把代价小的置零，因为代价会累积，而且我们注意到，每个数至多被操作1次，因为如果要操作两次，那么前一次的操作就没有什么意义，因为第二次操作又把他变成零了，所以我们可以把前一次的操作去除，也就是只进行第二次操作，这样也就只进行了一次操作
• 根据上面的分析，那么我们可以将两个数组中的数字组合到一起然后从小到大排一个序，cpp中可以使用pair，然后怎么得到最小的操作次数了，因为我们可操作的次数至多是n，那么我们可以试着枚举一下操作的次数，然后判断如果操作i次是不是可以满足要求，如果满足要求那么就可以直接返回了
• 但是怎么判断i次操作是不是可以满足要求呢，我们可以计算一下，操作i次可以减少的最大代价，然后我们可以用总代价减去可以减少的最大代价，这样就得出了当前操作次数下可以得到的最小总和，我们可以用动态规划来实现
• 我们定义一个f[i][j]表示前i个数中，操作j次可以减少的最大代价，那么当前数就有两种状态，选或者不选，如果不选，那么可以减少的最大代价就是前i - 1个数字中操作j次可以减少的最大代价，根据定义也就是f[i - 1][j]，如果当前状态选，也就是说当前可以减少的最大代价是前i - 1个数字中操作j - 1次(根据上面的分析，最后一次要操作第i个数)可减少的最大代价，加上操作最后一个数字可以减少的最大代价，因为是最后一次操作，那么如果第i次不操作，那么第i个数会变成i * nums_2[i] + nums_1[i]，也就是增加的代价加上本身的原来的值，操作之后变成0，那么最后一次操作可以减少的代价就是这个数字，写成表达式就是f[i - 1][j - 1] + i * nums_2[i] + nums_1[i]，因此状态转移就是f[i][j] = max(f[i - 1][j], f[i - 1][j - 1] + i * nums_2[i] + nums_1[i])，那么怎么判断是不是满足条件呢，假设nums_1的一开始的总和是sum1, nums_2的一开始的总和是sum2,那么总和i次操作后的最小和是sum1 + sum2 * i - f[n][i] ，那么代码就很好实现了

排序 + 动态规划

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

时间复杂度：$O(n^2)$

空间复杂度：$O(n^2)$

注意到，当前状态只和前一个状态有关系，那么我们可以优化掉一维，但是我们要将第二层枚举的的顺序要修改一下，由从小到大， 改成从大到小dp，原因和01背包问题是一样的

优化dp

此时状态定义可以理解为f[i]表示操作i次可以减少的最大代价

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

时间复杂度：$O(n^2)$

空间复杂度：$O(n)$

结束了