题目描述：
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：
- 选择任一满足
0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。
同时给你一个整数 x 。
请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。
数据范围：
$1\le nums.len \le 10^3, 1\le nums1[i] \le 10^3, 0\le nums2[i] \le 10^3, 0 \le x\le 10^6$
题解：
首先，每个位置只需要被操作一次，因为如果操作了两次，那么前一次无效，可以直接操作最后一次就行。
而且这个操作顺序应该与 $nums2$ 的大小有关。如果先操作大的，那么操作之后的时间，他会从 $0$ 开始增加，增加的最多。因此应该从小到大操作。
假设进行了 $j$ 次操作，操作的下标分别为 $i_1, i_2, \cdots, i_j$ ，那么对于这些操作，每次可以减少的值为：
从这个角度也可以发现，应该让较大的元素放在后面操作。需要对 $nums_1$ 和 $nums_2$ 按照 $nums_2$ 的元素值从小到大排列。
考虑动态规划，使用 $dp[i][j]$ 表示对于数组 $nums_1$ 的前 $i$ 个元素，进行了 $j$ 次操作，所能减少的元素和的最大值。后面可以枚举操作次数 $j$ ，然后 $sum_1 + j \times sum_2 - dp[n][j]$ 可以得到剩余元素之和。
状态转移方程为：
最后枚举 $j \in [0, n]$ 找到最小的满足 $sum_1 + sum_2 \times j - dp[n][j] \le x$ 的 $j$ 即为答案。
也可以一维优化，因为 $dp[i- 1][j]$ 就是上一行的第 $j$ 列，可以倒序枚举 $j$ 更新 $dp$ 数组。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
int minimumTime(vector<int> &nums1, vector<int> &nums2, int x)
{
int n = nums1.size();
vector<pair<int, int>> nums(n);
for (int i = 0; i < n; ++i)
{
nums[i].first = nums1[i];
nums[i].second = nums2[i];
}
sort(nums.begin(), nums.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
{ return x.second < y.second; });
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= i; ++j)
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - 1] + nums[i - 1].first + nums[i - 1].second * j);
}
}
int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
for (int j = 0; j <= n; ++j)
{
if (sum1 + sum2 * j - dp[n][j] <= x)
{
return j;
}
}
return -1;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const static int INF = 0x3f3f3f3f;
const static long long INF_LL = 0x3f3f3f3f3f3f3f3f;
const static long long mod = 1e9 + 7;
int minimumTime(vector<int> &nums1, vector<int> &nums2, int x)
{
int n = nums1.size();
vector<pair<int, int>> nums(n);
for (int i = 0; i < n; ++i)
{
nums[i].first = nums1[i];
nums[i].second = nums2[i];
}
sort(nums.begin(), nums.end(), [&](const pair<int, int> &x, const pair<int, int> &y)
{ return x.second < y.second; });
vector<int> dp(n + 1);
for (int i = 1; i <= n; ++i)
{
for (int j = i; j >= 1; --j)
{
dp[j] = max(dp[j], dp[j - 1] + nums[i - 1].first + nums[i - 1].second * j);
}
}
int sum1 = accumulate(nums1.begin(), nums1.end(), 0);
int sum2 = accumulate(nums2.begin(), nums2.end(), 0);
for (int j = 0; j <= n; ++j)
{
if (sum1 + sum2 * j - dp[j] <= x)
{
return j;
}
}
return -1;
}
};
|