网站建设基础流程,海外社交平台推广,国外室内设计网站推荐,大一做家教的网站https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-x/ 给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒#xff0c;对于所有下标 0 i nums1.length #xff0c;nums1[i] 的值都增加 nums2[i] 。操作 完成后 #xff0c;你… https://leetcode.cn/problems/minimum-time-to-make-array-sum-at-most-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,22,33] [0,4,6] 。
第 2 秒我们对 i 1 进行操作得到 nums1 [01,0,63] [1,0,9] 。
第 3 秒我们对 i 2 进行操作得到 nums1 [11,02,0] [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作所以我们返回 3 。
示例 2输入nums1 [1,2,3], nums2 [3,3,3], x 4
输出-1
解释不管如何操作nums1 的和总是会超过 x 。提示1 nums1.length 103
1 nums1[i] 103
0 nums2[i] 103
nums1.length nums2.length
0 x 106题解 答案最大为n因为当操作n1次时代表有一个位置操作了两次则那个位置的第一次操作被浪费掉了。 所以可以遍历1到n即选i个元素计算操作之后的最小值 先选择增量值小的即nums2中值较小的第一个选择的位置对应的val,会后续增加(i-1)*val所以先选择nums2中值较小的 dp[i][j] 表示在前 i -1个元素中清除(收集)j个获得的最大收益
初始化 f[0][0]0。
考虑第i 个数「选或不选」
不选
f[i1][j]f[i][j]。
选
f[i1][j]f[i][j−1]nums1[i]nums2[i]⋅j。
这两种情况取最大值即
f[i1][j]max(f[i][j],f[i][j−1]nums1[i]nums2[i]⋅j)code
class Solution {
public:int minimumTime(vectorint nums1, vectorint nums2, int x) {int n nums1.size();typedef pairint, int my_pair;// 所有元素按 nums2[i] 从小到大排序保证无后效性vectormy_pair vec;for (int i 0; i n; i) vec.push_back(my_pair(nums2[i], nums1[i]));sort(vec.begin(), vec.end());// 套用 0-1背包 dp 方程const long long INF 1e18;long long dp[n 1][n 1];for (int i 0; i n; i) for (int j 0; j n; j) dp[i][j] -INF;dp[0][0] 0;for (int i 1; i n; i) for (int j 0; j i; j) {f[i][j] f[i - 1][j];if (j 0) dp[i][j] max(dp[i][j], dp[i - 1][j - 1] vec[i - 1].second j * vec[i - 1].first);}// 枚举所有操作可能的次数long long sm1 0, sm2 0;for (int x : nums1) sm1 x;for (int x : nums2) sm2 x;for (int i 0; i n; i) {long long t sm1 sm2 * i - dp[n][i];if (t x) return i;}return -1;}
};维度压缩
class Solution {
public:int minimumTime(vectorint nums1, vectorint nums2, int x) {int n nums1.size();typedef pairint, int my_pair;// 所有元素按 nums2[i] 从小到大排序保证无后效性vectormy_pair vec;for (int i 0; i n; i) vec.push_back(my_pair(nums2[i], nums1[i]));sort(vec.begin(), vec.end());// 套用 dp 方程const long long INF 1e18;long long dp[n 1];for (int i 0; i n; i) dp[i] -INF;dp[0] 0;for (int i 1; i n; i) for (int j n; j 0; j--) {dp[j] max(dp[j], dp[j - 1] vec[i - 1].second j * vec[i - 1].first);}// 枚举所有操作可能的次数long long sm1 0, sm2 0;for (int x : nums1) sm1 x;for (int x : nums2) sm2 x;for (int i 0; i n; i) {long long t sm1 sm2 * i - dp[i];if (t x) return i;}return -1;}
};
