ধরুন x-অক্ষে একটি এক-মাত্রিক বাগান আছে৷ বাগানের শুরুর অবস্থান হল 0, এবং শেষের অবস্থান হল n৷ বাগানে [0, 1, ..., n] পয়েন্টে n + 1 ট্যাপ রয়েছে। যদি আমাদের একটি পূর্ণসংখ্যা n এবং একটি পূর্ণসংখ্যা অ্যারে রেঞ্জের দৈর্ঘ্য n + 1 থাকে যেখানে রেঞ্জ[i] হয় i-th ট্যাপ এলাকাটিকে জল দিতে পারে [i - ranges[i], i + ranges[i]] যখন সেই এলাকা খুলুন৷
৷আমাদের ন্যূনতম সংখ্যক ট্যাপ খুঁজে বের করতে হবে যেগুলি পুরো বাগানে জল দেওয়ার জন্য খোলা থাকবে, যদি কোনও সম্ভাব্য সমাধান না হয় তবে ফিরে আসুন -1।
সুতরাং, যদি ইনপুটটি n =5, এবং রেঞ্জ =[3,4,1,1,1,0] এর মত হয়, তাহলে আউটপুট হবে 1, যেমন দ্বিতীয় ট্যাপ থেকে, এটি পুরো গ্রাউন্ডকে কভার করবে [-3 থেকে 5]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আকারের একটি অ্যারে (n + 1) সংজ্ঞায়িত করুন এবং এটি -1
দিয়ে পূরণ করুন -
আরম্ভ করার জন্য i :=0, যখন i <=n, আপডেট করুন (i 1 দ্বারা বাড়ান), করবেন −
-
u :=সর্বাধিক i - রেঞ্জ[i] এবং 0
-
e :=সর্বনিম্ন n এবং i + রেঞ্জ[i]
-
v[u] :=সর্বাধিক v[u] এবং e
-
-
যদি v[0] -1 এর মত হয়, তাহলে −
-
রিটার্ন -1
-
-
curr :=v[0]
-
i :=0, পরবর্তী :=0
-
যখন curr
-
যখন আমি <=curr, do −
-
পরবর্তী :=পরের সর্বাধিক এবং v[i]
-
(i 1 দ্বারা বাড়ান)
-
-
যদি পরেরটি curr এর মত হয়, তাহলে −
-
রিটার্ন -1
-
-
curr :=পরবর্তী
-
(রেট 1 দ্বারা বৃদ্ধি করুন)
-
-
রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minTaps(int n, vector<int>& ranges) {
int ret = 1;
vector<int> v(n + 1, -1);
for (int i = 0; i <= n; i++) {
int u = max(i - ranges[i], 0);
int e = min(n, i + ranges[i]);
v[u] = max(v[u], e);
}
if (v[0] == -1)
return -1;
int curr = v[0];
int i = 0;
int next = 0;
while (curr < n) {
while (i <= curr) {
next = max(next, v[i]);
i++;
}
if (next == curr)
return -1;
curr = next;
ret++;
}
return ret;
}
};
main(){
Solution ob;
vector<int> v = {3,4,1,1,1,0};
cout << (ob.minTaps(5, v));
} ইনপুট
5, {3,4,1,1,1,0} আউটপুট
1
