给你两个长度相等下标从 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,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 。
示例 2:
输入:nums1 = [1,2,3], nums2 = [3,3,3], x = 4 输出:-1 解释:不管如何操作,nums1 的和总是会超过 x 。
看不懂OK
class Solution {
public:
int minimumTime(vector<int> &nums1, vector<int> &nums2, int x) {
int n = nums1.size();
// 对下标数组排序,避免破坏 nums1 和 nums2 的对应关系
vector<int> ids(n);
iota(ids.begin(), ids.end(), 0);
sort(ids.begin(), ids.end(), [&](const int i, const int j) {
return nums2[i] < nums2[j];
});
vector<int> f(n + 1);
for (int i = 0; i < n; i++) {
int a = nums1[ids[i]], b = nums2[ids[i]];
for (int j = i + 1; j; j--) {
f[j] = max(f[j], f[j - 1] + a + b * j);
}
}
int s1 = accumulate(nums1.begin(), nums1.end(), 0);
int s2 = accumulate(nums2.begin(), nums2.end(), 0);
for (int t = 0; t <= n; t++) {
if (s1 + s2 * t - f[t] <= x) {
return t;
}
}
return -1;
}
};
给你一个下标从 0 开始的二维整数数组 dimensions
。
对于所有下标 i
(0 <= i < dimensions.length
),dimensions[i][0]
表示矩形 i
的长度,而 dimensions[i][1]
表示矩形 i
的宽度。
返回对角线最 长 的矩形的 面积 。如果存在多个对角线长度相同的矩形,返回面积最 大 的矩形的面积。
示例 1:
输入:dimensions = [[9,3],[8,6]] 输出:48 解释: 下标 = 0,长度 = 9,宽度 = 3。对角线长度 = sqrt(9 * 9 + 3 * 3) = sqrt(90) ≈ 9.487。 下标 = 1,长度 = 8,宽度 = 6。对角线长度 = sqrt(8 * 8 + 6 * 6) = sqrt(100) = 10。 因此,下标为 1 的矩形对角线更长,所以返回面积 = 8 * 6 = 48。
示例 2:
输入:dimensions = [[3,4],[4,3]] 输出:12 解释:两个矩形的对角线长度相同,为 5,所以最大面积 = 12。
提示:
1 <= dimensions.length <= 100
dimensions[i].length == 2
1 <= dimensions[i][0], dimensions[i][1] <= 100
sqrt出来的是double,不能用int接收。
class Solution {
public:
int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
if(dimensions.empty()) return 0;
int max_diagonal = 0, max_l = 0, l = 0;
for(const auto& dim : dimensions){
l = dim[0] * dim[0] + dim[1] * dim[1];
if(l > max_l || (l == max_l && dim[0] * dim[1] > max_diagonal)){
max_diagonal = dim[0] * dim[1];
max_l = l;
}
}
return max_diagonal;
}
};