ধরি x-অক্ষ trên একটি এক-মাত্রিক বাগান আছে। বাগানের শুরু 0 এবং শেষ n। বাগানে n+1টি ট্যাপ আছে [0, 1, ..., n] পয়েন্টে। ranges[i] হলো i-তম ট্যাপটি খোলা থাকলে [i - ranges[i], i + ranges[i]] এরিয়া পানি দেবে।
পুরো বাগান পানি দিতে ন্যূনতম কতটি ট্যাপ খোলা দরকার তা বের করতে হবে। সম্ভব না হলে -1 ফেরত দিন।
ইনপুট যদি n = 5, ranges = [3,4,1,1,1,0] হয়, তবে আউটপুট 1, কারণ দ্বিতীয় ট্যাপ থেকে পুরো জমি [-3 থেকে 5] কভার হয়।
সমাধানের ধাপসমূহ
n+1 আকারের একটি v অ্যারে -1 দিয়ে ফিল করুন
i := 0 থেকে n পর্যন্ত লুপ চালান –
u := max(i - ranges[i], 0)
e := min(n, i + ranges[i])
v[u] := max(v[u], e)
যদি v[0] == -1 হয়, তবে -1 ফেরত দিন
curr := v[0]
i := 0, next := 0, ret := 1
যখন curr < n, লুপ চালান –
যখন i <= curr, লুপ চালান –
next := max(next, v[i])
i++
যদি next == curr হয়, তবে -1 ফেরত দিন
curr := next
ret++
ret ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#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
