C++で水平および垂直にカットした後のケーキの最大面積

高さh、幅wの長方形のケーキがあるとすると、整数の2つの配列horizo​​ntalCutsとverticalCutsがあります。ここで、horizo​​ntalCuts [i]は、長方形のケーキの上部からi番目の水平カットまでの距離を表します。同様にverticalCuts [j]長方形のケーキの左側からj番目の垂直カットまでの距離を表します。

配列horizo​​ntalCutsとverticalCutsで提供される水平方向と垂直方向の各位置でケーキをカットした後、ケーキの最大面積を見つける必要があります。答えは大きい可能性があるため、このモジュロ10 ^ 9+7を返します。

したがって、入力がh =5、w =4、horizo​​ntalCuts =[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を挿入します

• インデックス0にあるvvの最初の要素をvvに挿入します

• vvの最後にwを挿入します

• a：=0、b：=0

• 初期化i：=1の場合、i

  • a：=aとhh[i]の最大値-hh[i-1]

• 初期化i：=1の場合、i

  • 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