题目描述
给你两个长度相等下标从 0 开始的整数数组 nums1
和 nums2
。每一秒,对于所有下标 0 <= i < nums1.length
,nums1[i]
的值都增加 nums2[i]
。操作 完成后,你可以进行如下操作:
- 选择任一满足
0 <= i < nums1.length
的下标i
,并使nums1[i] = 0
。
同时给你一个整数 x
。
请你返回使 nums1
中所有元素之和 小于等于 x
所需要的 最少 时间,如果无法实现,那么返回 -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。
输入: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
算法
(贪心,动态规划) $O(n^2)$
- 显然,每一秒结束后都执行一次清零操作是最优的,故可以将操作次数与秒数等价。
- 每个下标最多操作一次清零。不然的话,可以只保留最后一次的清零操作,答案不会变差。
- 尽可能的先清零 $nums2$ 较小的下标,后清零 $nums2$ 较大的下标。不然的话,可以交换不符合要求下标对的清零顺序,会使答案变优。故可以将 $nums2$ 从小到大排序,然后按顺序考虑每个下标是否需要清零。
- 考虑动态规划,设 $f(i, j)$ 表示前 $i$ 个位置,用了 $j$ 次清零操作后得到的前 $i$ 个位置的最小元素之和。其中 $i$ 的有限范围是 $[1, n]$,$j$ 的范围是 $[0, n]$。
- 初始时,$f(0, 0) = 0$,其余为正无穷待定。
- 转移时,对于 $f(i, j)$,当前下标可以选择不执行清零操作,需要加上代价 $nums1(i) + j \cdot nums2(i)$。如果 $j > 0$ 则可以选择第 $j$ 次对当前位置执行清零操作,代价是 $\sum_{k=1}^{i}{nums1(k)}$,这部分的代价可以用一个变量实时计算。
- 最终答案为最小的 $j$,满足 $f(n, j) \le x$。如果不存在,则返回 $-1$。
- 第二维可以采用倒序枚举,优化掉第一维的状态表示。
时间复杂度
- 排序预处理的时间复杂度为 $O(n \log n)$。
- 动态规划的状态数为 $O(n^2)$,转移时间为常数。
- 故总时间复杂度为 $O(n^2)$。
空间复杂度
- 采用倒序枚举第二维,仅需要 $O(n)$ 的额外空间存储预处理排序后的下标数组,排序的系统栈,和动态规划的状态。
C++ 代码
class Solution {
public:
int minimumTime(vector<int>& nums1, vector<int>& nums2, int x) {
const int n = nums1.size();
const int INF = 1000000000;
vector<int> id(n);
for (int i = 0; i < n; i++)
id[i] = i;
sort(id.begin(), id.end(), [&](int x, int y) {
return nums2[x] < nums2[y];
});
vector<int> f(n + 1, INF);
f[0] = 0;
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j >= 0; j--) {
f[j] += nums1[id[i]] + j * nums2[id[i]];
if (j > 0)
f[j] = min(f[j], f[j - 1] + sum);
}
sum += nums2[id[i]];
}
for (int j = 0; j <= n; j++)
if (f[j] <= x)
return j;
return -1;
}
};