मान लीजिए कि x-अक्ष पर एक आयामी बगीचा है। बगीचे की प्रारंभिक स्थिति 0 है, और समाप्ति स्थिति n है। बगीचे में बिंदु [0, 1, ..., n] पर स्थित n + 1 नल हैं। यदि हमारे पास एक पूर्णांक n है और एक पूर्णांक सरणी लंबाई n + 1 है, जहां रेंज [i] i-th टैप क्षेत्र को पानी दे सकता है [i - रेंज [i], i + रेंज [i]] जब वह क्षेत्र है खुला।
हमें कम से कम नलों की संख्या ज्ञात करनी है जो पूरे बगीचे में पानी भरने के लिए खुले हों, यदि कोई समाधान संभव नहीं है, तो -1 को वापस कर दें।
इसलिए, यदि इनपुट n =5, और रेंज =[3,4,1,1,1,0] जैसा है, तो आउटपुट 1 होगा, जैसा कि दूसरे टैप से, यह पूरे मैदान को कवर करेगा [-3 से 5]।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
एक सरणी v आकार (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
-
-
वर्तमान:=वी[0]
-
मैं :=0, अगला :=0
-
जबकि curr
-
जबकि मैं <=curr, करते हैं -
-
अगला:=अगले का अधिकतम और v[i]
-
(i 1 से बढ़ाएँ)
-
-
अगर अगला कर्व के समान है, तो -
-
वापसी -1
-
-
वर्तमान:=अगला
-
(रिटर्न 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