मान लीजिए हमारे पास संख्याओं का एक ऐरे A है, जिसमें i-वीं संख्या वह स्थान है जहां एक द्वीप मौजूद है, और एक और पूर्णांक k दिया गया है (1 ≤ k < N)। अब, एक व्यक्ति 0-वें द्वीप पर खड़ा है और उसे अंतिम द्वीप तक पहुंचना है, एक द्वीप से दूसरे द्वीप पर कूदकर ठीक k कूद में। हमें उस अधिकतम कूद की लंबाई का न्यूनतम मान ढूंढना है जो व्यक्ति अपनी यात्रा में करेगा। ध्यान रखें कि सभी द्वीपों की स्थितियां आरोही क्रम में दी गई हैं।
तो, यदि इनपुट A = [7, 20, 41, 48], k = 2 जैसा है, तो आउटपुट 28 होगा, क्योंकि अंतिम द्वीप तक पहुंचने के दो तरीके हैं: 7 से 20 से 48, यहां किन्हीं दो लगातार द्वीपों के बीच अधिकतम दूरी 48 और 20 के बीच है जो 28 है। और 7 से 41 से 48, यहां अधिकतम दूरी 41 और 7 के बीच है जो 34 है। तो, 28 और 34 का न्यूनतम 28 है।
इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे:
isPossible() फंक्शन परिभाषित करें। यह arr, dist, k लेगा।
n := arr का आकार
req := 0
current := 0
previous := 0
i को 0 से n तक के लिए, करें:
जब current, n के समान नहीं है और (arr[current] - arr[previous]) <= dist, करें:
current := current + 1
req := req + 1
यदि current, n के समान है, तो:
लूप से बाहर निकलें
previous := current - 1
यदि current, n के समान नहीं है, तो:
False लौटाएं
यदि req <= k, तो:
True लौटाएं
False लौटाएं
मुख्य विधि से, निम्नलिखित करें:
n := arr का आकार
left := 0
right := arr का अंतिम तत्व
ans := 0
जब left <= right, करें:
mid := (left + right) / 2;
यदि isPossible(arr, mid, k) शून्येतर है, तो:
ans := mid
right := mid - 1
अन्यथा,
left := mid + 1
ans लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:
def isPossible(arr,dist, k) : n = len(arr) req = 0 current = 0 previous = 0 for i in range(0, n): while (current != n and (arr[current] - arr[previous]) <= dist): current += 1 req += 1 if (current == n): break previous = current - 1 if (current != n): return False if (req <= k): return True return False def minimum_distance(arr, k): n = len(arr) left = 0 right = arr[-1] ans = 0 while (left <= right): mid = (left + right) // 2; if (isPossible(arr, mid, k)): ans = mid right = mid - 1 else: left = mid + 1 return ans arr = [7, 20, 41, 48] k = 2 print(minimum_distance(arr, k))
इनपुट
[7, 20, 41, 48] , 2
आउटपुट
28
