题目:使数组和小于等于x的最小时间
给你两个长度相等下标从 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 。
解题思路:
每一秒,对于所有下标 0 <= i < nums1.length
,nums1[i]
的值都增加 nums2[i],
观察重置为零的数,会按照 nums2的速度增长,所以对于所有操作的数,我们应该优先操作增长速度慢的数。这样就可以出去更多的数。最终结果应为nums1的和加上nums2的和再减去可以消掉的最大数目。
让我们按照 nums2 的大小对所有数值对进行排序(非递减顺序)。用 dp[j][i] 表示如果对前 j 个元素进行 i次操作,可以减少的最大总值,初始值为零。对于第 j 个元素,我们可以选择对其进行操作或者不操作,由此可以得到状态转移方程:dp[j][i]=max(dp[j−1][i],dp[j−1][i−1]+nums2[j−1]×i+nums1[j−1])
其中有 1≤i≤j≤n。
最后我们返回最小的 t,使满足 sum(nums1)+sum(nums2)×t−dp[n][t]≤x,如果不存在返回 −1。
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;
}
};