พื้นที่สูงสุดของชิ้นเค้กหลังจากการตัดแนวนอนและแนวตั้งใน C++

สมมติว่าเรามีเค้กรูปสี่เหลี่ยมผืนผ้าที่มีความสูง h และความกว้าง w เรายังมีอาร์เรย์ของจำนวนเต็มจำนวนเต็ม horizontalCuts และ verticalCuts สองอาร์เรย์ โดยที่ horizontalCuts[i] แทนระยะห่างจากด้านบนของเค้กสี่เหลี่ยมถึง ith ในแนวนอน และในทำนองเดียวกัน 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 ที่ดัชนี 0 ลงใน hh

• ใส่ h ต่อท้าย hh

• แทรกองค์ประกอบแรกของ vv ที่ดัชนี 0 ลงใน vv

• ใส่ w ต่อท้าย vv

• a :=0, b :=0

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของ hh อัปเดต (เพิ่ม i ขึ้น 1) ทำ -

  • a :=สูงสุดของ a และ hh[i] - hh[i - 1]

• สำหรับการเริ่มต้น i :=1 เมื่อฉัน <ขนาดของ 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