Computer >> Máy Tính >  >> Lập trình >> C ++

Diện tích tối đa của một miếng bánh sau khi cắt ngang và cắt dọc trong C ++

Giả sử chúng ta có một chiếc bánh hình chữ nhật với chiều cao h và chiều rộng w, chúng ta cũng có hai mảng số nguyên là verticalCuts và verticalCuts trong đó verticalCuts [i] biểu thị khoảng cách từ đỉnh của chiếc bánh hình chữ nhật đến đường cắt ngang thứ i và tương tự, verticalCuts [j] thể hiện khoảng cách từ bên trái của chiếc bánh hình chữ nhật đến vết cắt dọc thứ j.

Chúng ta phải tìm diện tích lớn nhất của một miếng bánh sau khi chúng ta cắt nó ở mỗi vị trí ngang và dọc được cung cấp trong mảng NgangCuts và Cắt dọc. Câu trả lời có thể lớn, vì vậy hãy trả về modulo này 10 ^ 9 + 7.

Vì vậy, nếu đầu vào giống như h =5, w =4, verticalCuts =[1,2,4], verticalCuts =[1,3]

thì đầu ra sẽ là 4, vì từ hình ảnh đó, chúng ta có thể hiểu chiếc bánh hình chữ nhật đã cho.

Các đường màu đỏ là các đường cắt ngang và dọc. Sau khi chúng tôi cắt bánh, miếng bánh màu xanh lá cây có diện tích tối đa.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • Xác định một hàm mul (), điều này sẽ nhận a, b,

  • return ((a mod m) * (b mod m)) mod m

  • Từ phương thức chính, chúng ta sẽ lấy h, w, một mảng hh, một mảng vv,

  • sắp xếp mảng hh và vv

  • chèn phần tử đầu tiên của hh, ở chỉ mục 0 vào hh

  • chèn h vào cuối hh

  • chèn phần tử đầu tiên của vv, tại chỉ mục 0 vào vv

  • chèn w vào cuối vv

  • a:=0, b:=0

  • để khởi tạo i:=1, khi i

    • a:=tối đa của a và hh [i] - hh [i - 1]

  • để khởi tạo i:=1, khi i

    • b:=tối đa là b và vv [i] - vv [i - 1]

  • trả về mul (a, b)

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn - 

#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));
}

Đầu vào 

5,4,{1,2,4}, {1,3}

Đầu ra 

4