ধরুন আমাদের একটি আয়তক্ষেত্রাকার কেক আছে যার উচ্চতা h এবং w প্রস্থ রয়েছে, আমাদের কাছে পূর্ণসংখ্যার দুটি অ্যারে রয়েছে horizontalCuts এবং verticalCuts যেখানে horizontalCuts[i] আয়তক্ষেত্রাকার কেকের উপরের দিক থেকে ith অনুভূমিক কাটা পর্যন্ত দূরত্বকে প্রতিনিধিত্ব করে এবং একইভাবে, উল্লম্ব কাট[j] আয়তক্ষেত্রাকার কেকের বাম থেকে jth উল্লম্ব কাটা পর্যন্ত দূরত্বের প্রতিনিধিত্ব করে।
অনুভূমিক এবং উল্লম্ব অবস্থানে প্রদত্ত অ্যারে হরিজন্টালকাটস এবং উল্লম্ব কাটে কেক কাটার পর আমাদের একটি টুকরোটির সর্বাধিক ক্ষেত্রফল খুঁজে বের করতে হবে। উত্তরটি বড় হতে পারে, তাই এই মডিউলটি 10^9 + 7 ফেরত দিন।
সুতরাং, যদি ইনপুটটি h =5, w =4, অনুভূমিক কাটা =[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
এ -
hh
এর শেষে h ঢোকান -
vv
-এ সূচক 0-এ vv-এর প্রথম উপাদান সন্নিবেশ করান -
vv
এর শেষে w সন্নিবেশ করান -
a :=0, b :=0
-
আরম্ভ করার জন্য i :=1, যখন i
-
a :=সর্বাধিক a এবং hh[i] - hh[i - 1]
-
-
আরম্ভ করার জন্য 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} আউটপুট
4
