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

https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/description/

代码

class Solution {
public:
    int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
        int n = nums1.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        vector<pair<int, int>> nums(n);
        for (int i = 0; i < n; i++) {
            nums[i] = {nums2[i], nums1[i]};
        }
        sort(nums.begin(), nums.end());

        for (int j = 1; j <= n; j++) {
            int b = nums[j - 1].first, a = nums[j - 1].second;
            for (int i = j; i > 0; i--) {
                dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);
            }
        }

        int s1 = accumulate(nums1.begin(), nums1.end(), 0);
        int s2 = accumulate(nums2.begin(), nums2.end(), 0);
        for (int i = 0; i <= n; i++) {
            if (s2 * i + s1 - dp[n][i] <= x) {
                return i;
            }
        }
        return -1;
    }
};

解释

逐行解释代码的功能：

int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {

这是 minimumTime 函数的声明，它接收两个整数向量 nums1 和 nums2，以及一个整数 x 作为参数。

int n = nums1.size();

这行代码初始化了一个整数 n，它是 nums1（和 nums2，因为它们长度相等）的长度。

vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

这里声明了一个二维向量 dp，大小为 (n+1) x (n+1)，所有元素初始化为 0。dp 用于动态规划，其中 dp[j][i] 将存储考虑到第 j 个元素和 i 次操作时的最佳结果。

vector<pair<int, int>> nums(n);

创建一个 pair 类型的向量 nums，长度为 n。每个元素都是一个包含来自 nums2 和 nums1 的值的对。

for (int i = 0; i < n; i++) {
    nums[i] = {nums2[i], nums1[i]};
}

这个循环填充 nums 向量，每个元素都是一个由 nums2[i] 和 nums1[i] 组成的对，这个对可能用于后续的排序和决策。

sort(nums.begin(), nums.end());

对 nums 向量进行排序，默认情况下是按照第一个元素（也就是 nums2 的值）进行升序排序。

for (int j = 1; j <= n; j++) {

这个循环通过 j 来迭代 nums 向量的每个元素。

int b = nums[j - 1].first, a = nums[j - 1].second;

提取 nums 中的第 j-1 个元素对，将 nums2 的值赋给 b，将 nums1 的值赋给 a。

for (int i = j; i > 0; i--) {

这个内部循环倒序迭代从 j 到 1 的每个值，用于更新 dp 数组。

dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);

更新 dp[j][i] 的值。这里它比较两个选项：不做操作（dp[j - 1][i]）和做操作（dp[j - 1][i - 1] + i * b + a），选择它们之间的最大值。

    }
}

这里闭合了内部 for 循环和外部 for 循环。

int s1 = accumulate(nums1.begin(), nums1.end(), 0);

计算 nums1 的元素总和。

int s2 = accumulate(nums2.begin(), nums2.end(), 0);

计算 nums2 的元素总和。

for (int i = 0; i <= n; i++) {

这个循环用于寻找最少的操作次数，使得 nums1 的总和加上每秒 nums2 产生的增量后不超过 x。

if (s2 * i + s1 - dp[n][i] <= x) {

检查在 i 次操作后，是否可以将 nums1 的总和减少到 x 或以下。这个条件利用了 dp 数组的结果来确定。

return i;

如果条件满足，则返回操作次数 `

状态转移方程

dp[j][i] = max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a);

这个动态规划（DP）的转移方程是这段代码中最关键的部分，它是决定 dp 数组如何更新的核心。

在这个上下文中，dp[j][i] 表示考虑前 j 个元素，并且进行了 i 次操作时 nums1 的元素总和的最大可能增量。这里的 “操作” 特指的是在每一秒钟结束时，选择一个 nums1 中的元素，并使其增加 nums2 中对应位置的值。

让我们分解这个方程：

• dp[j - 1][i]：
  这表示如果在当前秒不进行任何操作，nums1 的总和将与前一秒 j-1 时在 i 次操作下的总和相同。

• dp[j - 1][i - 1] + i * b + a：
  这是一个比较复杂的表达式，它表示如果在当前秒你选择进行操作，你能得到的 nums1 总和的最大增量。

  • dp[j - 1][i - 1]：这是前一秒在做了 i-1 次操作的情况下的最大总和增量。
  • i * b：因为每进行一次操作，nums2[j-1]（在代码中是 b）就会被加到 nums1 对应的元素上 i 次（因为已经经过了 i 秒），所以这里乘以 i。
  • a：这是 nums1[j-1] 在没有任何操作时本应该增加的值，在进行操作后这个增量依然会发生。

然后，max(dp[j - 1][i], dp[j - 1][i - 1] + i * b + a) 这部分比较了两种情况（操作或不操作）并选择了能够得到更大总和的那个选项。

因此，这个转移方程在每一步都在决定：给定当前我们正在考虑的元素（j 个），如果进行了 i 次操作，是继续保持当前的总和（不操作），还是通过增加对应 nums2 的值来尝试增加 nums1 的总和（操作），以便在不超过 x 的条件下达到最小的搬运时间。

这个决策过程在所有元素和所有可能的操作次数上累积起来，最终 dp[n][i] 会告诉我们在进行 i 次操作后能得到的 nums1 的最大总和增量。