मान लीजिए कि हमारे पास संख्याओं की एक सरणी A है, A में i-th संख्या वह स्थिति है जहां एक द्वीप मौजूद है, और दूसरा पूर्णांक k दिया गया है (1 ≤ k
इसलिए, यदि इनपुट ए =[7, 20, 41, 48], के =2 जैसा है, तो आउटपुट 28 होगा, क्योंकि अंतिम द्वीप 7 से 20 से 48 तक पहुंचने के दो तरीके हैं, यहां अधिकतम दूरी किन्हीं दो लगातार द्वीपों के बीच 48 और 20 के बीच यानी 28 है। और 7 से 41 से 48 तक यहां किन्हीं दो लगातार द्वीपों के बीच अधिकतम दूरी 41 और 7 के बीच है जो कि 34 है। तो, 28 और 34 की न्यूनतम 28 है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
एक फ़ंक्शन को परिभाषित करें isPosible() । यह गिरफ्तारी, जिला, कश्मीर ले जाएगा
n :=गिरफ्तारी का आकार
अनुरोध :=0
वर्तमान :=0
पिछला:=0
मेरे लिए 0 से n की सीमा में, करें
जबकि करंट n के समान नहीं है और (arr[current] - arr[previous]) <=dist, do
वर्तमान:=वर्तमान + 1
अनुरोध :=अनुरोध + 1
अगर करंट n के समान है, तो
लूप से बाहर आएं
पिछला:=वर्तमान - 1
अगर करंट n के समान नहीं है, तो
झूठी वापसी
अगर अनुरोध <=के, तो
सही लौटें
झूठी वापसी
मुख्य विधि से, निम्न कार्य करें -
n :=गिरफ्तारी का आकार
बायां :=0
दाएं:=गिरफ्तारी का अंतिम तत्व
उत्तर:=0
जबकि बाएँ −=दाएँ, करें
मध्य:=(बाएं + दाएं) / 2;
अगर संभव है (गिरफ्तारी, मध्य, के) गैर-शून्य है, तो
उत्तर :=मध्य
दाएं:=मध्य - 1
अन्यथा,
बायां :=मध्य + 1
वापसी उत्तर
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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
