在C ++中水平和垂直切割后一块蛋糕的最大面积

假设我们有一个矩形蛋糕，其高度为h，宽度为w，我们还有两个整数数组horizontalCuts和verticalCuts，其中horizontalCuts [i]表示从矩形蛋糕顶部到第i个水平切口的距离，类似地，verticalCuts [j]表示从矩形蛋糕的左侧到第j个垂直切口的距离。

在将水平蛋糕和垂直蛋糕阵列中提供的每个水平和垂直位置切开一块蛋糕后，我们必须找到一块蛋糕的最大面积。答案可能很大，因此返回此模10 ^ 9 + 7。

因此，如果输入像h = 5，w = 4，horizontalCuts = [1,2,4]，verticalCuts = [1,3]

那么输出将为4，因为从该图像中我们可以理解给定的矩形蛋糕。

红线是水平和垂直切割。切完蛋糕后，绿色的蛋糕面积最大。

为了解决这个问题，我们将遵循以下步骤-

• 定义一个函数mul()，它将花费a，b，

• return（（a mod m）*（b mod m））mod m

• 从main方法中，我们将得到h，w，一个数组hh，一个数组vv，

• 对数组hh和vv排序

• 将hh的第一个元素（在索引0处）插入hh

• 在hh的末尾插入h

• 在索引vv中插入vv的第一个元素

• 在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