मान लीजिए x-अक्ष पर एक आयामी बगीचा है। बगीचे की शुरुआती स्थिति 0 है, और अंतिम स्थिति n है। बगीचे में बिंदुओं [0, 1, ..., n] पर n + 1 नल स्थित हैं। यदि हमारे पास एक पूर्णांक n और लंबाई n + 1 की एक पूर्णांक सरणी ranges है जहां 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 से भरें
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;
}
};
int main() {
Solution ob;
vector<int> v = {3,4,1,1,1,0};
cout << (ob.minTaps(5, v));
return 0;
}
इनपुट
5, {3,4,1,1,1,0}
आउटपुट
1