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

สมมติว่าเรามีเค้กสี่เหลี่ยมผืนผ้า สูง h กว้าง w มี horizontalCuts และ verticalCuts แสดงตำแหน่งการตัด เราต้องหาพื้นที่สูงสุดของชิ้นเค้กหลังตัดทุกตำแหน่ง คำตอบ modulo 10^9+7

ตัวอย่าง: h=5, w=4, horizontalCuts=[1,2,4], verticalCuts=[1,3] ผลลัพธ์ = 4

วิธีแก้ปัญหา

1. เรียง horizontalCuts และ verticalCuts
2. เพิ่ม 0 และ h/w เข้าไปในอาร์เรย์ตามลำดับ
3. หาช่องว่างสูงสุดระหว่างตัดติดกันในแนวนอน (a) และแนวตั้ง (b)
4. พื้นที่สูงสุด = a * b mod 1e9+7

ตัวอย่างโค้ด C++

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

int 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