सी ++ में क्षैतिज और लंबवत कटौती के बाद केक के टुकड़े का अधिकतम क्षेत्रफल

मान लीजिए कि हमारे पास ऊंचाई h और चौड़ाई w के साथ एक आयताकार केक है, हमारे पास पूर्णांक क्षैतिज कट और लंबवत कट के दो सरणी भी हैं जहां क्षैतिज कट [i] आयताकार केक के शीर्ष से क्षैतिज कट तक की दूरी का प्रतिनिधित्व करता है और इसी तरह, लंबवत कट [जे] आयताकार केक के बाईं ओर से jth वर्टिकल कट तक की दूरी को दर्शाता है।

केक के एक टुकड़े का अधिकतम क्षेत्रफल ज्ञात करने के लिए जब हम इसे क्षैतिज कट और ऊर्ध्वाधर कट में प्रदान की गई प्रत्येक क्षैतिज और ऊर्ध्वाधर स्थिति में काटते हैं। उत्तर बड़ा हो सकता है, इसलिए यह मॉड्यूल 10^9 + 7 लौटाएं।

इसलिए, यदि इनपुट h =5, w =4, हॉरिज़ॉन्टलकट्स =[1,2,4], वर्टिकलकट्स =[1,3]

तो आउटपुट 4 होगा, क्योंकि उस इमेज से हम दिए गए आयताकार केक को समझ सकते हैं।

लाल रेखाएँ क्षैतिज और ऊर्ध्वाधर कट हैं। केक काटने के बाद, केक के हरे टुकड़े का क्षेत्रफल अधिकतम होता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• फ़ंक्शन mul() को परिभाषित करें, इसमें a, b,

  . लगेगा

• वापसी ((एक मॉड एम) * (बी मॉड एम)) मॉड एम

• मुख्य विधि से हम h, w, एक सरणी hh, एक सरणी vv,

  . लेंगे

• सरणी hh और vv को सॉर्ट करें

• एचएच के पहले तत्व को इंडेक्स 0 पर एचएच में डालें

• hh के अंत में h डालें

• vv का पहला तत्व डालें, सूचकांक 0 पर vv में

• vv के अंत में w डालें

• ए:=0, बी:=0

• इनिशियलाइज़ i के लिए:=1, जब i

  • a :=अधिकतम a और hh[i] - hh[i - 1]

• इनिशियलाइज़ i :=1 के लिए, जब i

  • b :=अधिकतम b और vv[i] - vv[i - 1]

• वापसी मूल (ए, बी)

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

#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