C++에서 수평 및 수직 절단 후 케이크 조각의 최대 면적

<시간/>

높이가 h이고 너비가 w인 직사각형 케이크가 있다고 가정하고, HorizontalCuts[i]가 직사각형 케이크의 상단에서 i번째 수평 절단까지의 거리를 나타내는 두 개의 정수 horizontalCuts 및 verticalCuts가 있다고 가정하고, 유사하게 verticalCuts[j] 직사각형 케이크의 왼쪽에서 j번째 수직 절단까지의 거리를 나타냅니다.

HorizontalCuts 및 verticalCuts 배열에 제공된 각 수평 및 수직 위치에서 케이크 조각을 자른 후 최대 면적을 찾아야 합니다. 답이 클 수 있으므로 이 모듈로 10^9 + 7을 반환하십시오.

따라서 입력이 h =5, w =4, horizontalCuts =[1,2,4], verticalCuts =[1,3]

와 같은 경우

그러면 해당 이미지에서 주어진 직사각형 케이크를 이해할 수 있으므로 출력은 4가 됩니다.

빨간색 선은 가로 및 세로 절단입니다. 케이크를 자르고 나면 녹색 케이크 조각의 면적이 최대가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

mul() 함수를 정의하면, b,
return ((a mod m) * (b mod m)) mod m
주요 방법에서 우리는 h, w, 배열 hh, 배열 vv,
를 취할 것입니다.
배열 hh 및 vv 정렬
인덱스 0에서 hh의 첫 번째 요소를 hh에 삽입
hh 끝에 h 삽입
vv의 인덱스 0에 있는 vv의 첫 번째 요소 삽입
vv 끝에 w 삽입
a :=0, b :=0
initialize i :=1의 경우 i
- a :=a 및 hh[i]의 최대값 - hh[i - 1]
for initialize 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}