C++ 中水平和垂直切割后蛋糕的最大面积
假设我们有一个高为 h、宽为 w 的矩形蛋糕，我们有两个整数数组:horizontalCuts 和 VerticalCuts，其中 HorizontalCuts[i] 表示从矩形蛋糕顶部到第 i 个水平切割点的距离，类似地，verticalCuts[j] 表示从矩形蛋糕左侧到第 j 个垂直切割点的距离。
我们需要在数组 HorizontalCuts 和 VerticalCuts 中提供的每个水平和垂直位置切割蛋糕后，找到蛋糕的最大面积。答案可能很大，因此返回对 10^9 + 7 取模的结果。
因此，如果输入为 h = 5、w = 4、horizontalCuts = [1,2,4]、verticalCuts = [1,3]
那么输出将为 4，因为从该图像中我们可以理解给定的矩形蛋糕。
红线是水平和垂直切口。切开蛋糕后，绿色蛋糕的面积最大。
为了解决这个问题，我们将遵循以下步骤 −
定义一个函数 mul()，它将接受 a, b,
返回 ((a mod m) * (b mod m)) mod m
从 main 方法中，我们将接受 h, w, 一个数组 hh, 一个数组 vv,
对数组 hh 和 vv 进行排序
将 hh 的第一个元素(索引 0 处)插入到 hh 中
将 h 插入到 hh 的末尾
将 vv 的第一个元素(索引 0 处)插入到 vv 中
将 w 插入到vv
a := 0, b := 0
初始化 i := 1，当 i < hh 的大小时，更新 i(将 i 加 1)，执行 −
a := a 和 hh[i] - hh[i - 1] 中的最大值
初始化 i := 1，当 i < vv 的大小时，更新 i(将 i 加 1)，执行 −
b := b 和 vv[i] - vv[i - 1] 中的最大值
返回 mul(a, b)
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
typedef long long int lli;
class Solution {
public:
lli mul(lli a, lli b){
return ((a % mod) * (b % mod)) % mod;
}
int maxArea(int h, int w, vector<int>& hh, vector<int>& vv) {
sort(hh.begin(), hh.end());
sort(vv.begin(), vv.end());
hh.insert(hh.begin(), 0);
hh.push_back(h);
vv.insert(vv.begin(), 0);
vv.push_back(w);
int a = 0;
int b = 0;
for (int i = 1; i < hh.size(); i++) {
a = max(a, hh[i] - hh[i - 1]);
}
for (int i = 1; i < vv.size(); i++) {
b = max(b, vv[i] - vv[i - 1]);
}
return mul(a, b);
}
};
main(){
Solution ob;
vector<int> v = {1,2,4}, v1 = {1,3};
cout << (ob.maxArea(5,4,v,v1));
}
输入
5,4,{1,2,4}, {1,3}
输出
4
