数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究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
从主方法中，我们将获取 h、w、数组 hh、数组 vv，
对数组 hh 和 vv 进行排序
将 hh 的第一个元素插入到 hh 的索引 0 处
在 hh 的末尾插入 h
将 vv 的第一个元素插入到 vv 的索引 0 处
在 vv 的末尾插入 w
a := 0，b := 0
对于初始化 i := 1，当 i < hh 的大小，更新（i 增加 1），执行：
a := a 和 hh[i] - hh[i - 1] 的最大值
对于初始化 i := 1，当 i < vv 的大小，更新（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
159 次查看
