ধরুন আমাদের কাছে সংখ্যার একটি অ্যারে আছে, A-তে i-তম সংখ্যা হল সেই অবস্থান যেখানে একটি দ্বীপ রয়েছে, এবং আরেকটি পূর্ণসংখ্যা k দেওয়া হয়েছে (1 ≤ 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 এর আকার
অনুরোধ :=0
বর্তমান :=0
আগের :=0
0 থেকে n রেঞ্জের জন্য, করুন
যদিও বর্তমান n এবং (arr[বর্তমান] - arr[পূর্ববর্তী]) <=dist, do
বর্তমান :=বর্তমান + 1
req :=req + 1
যদি বর্তমান n এর মত হয়, তাহলে
লুপ থেকে বেরিয়ে আসুন
পূর্ববর্তী :=বর্তমান - 1
যদি কারেন্ট n এর মত না হয়, তাহলে
রিটার্ন ফলস
যদি req <=k, তাহলে
রিটার্ন ট্রু
রিটার্ন ফলস
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
n :=arr এর আকার
বাম :=0
ডানে :=অ্যারের শেষ উপাদান
উত্তর :=0
যখন বাম -=ডান, কর
মধ্য :=(বাম + ডান) / 2;
যদি isPossible(arr, mid, k) অ-শূন্য হয়, তাহলে
উত্তর :=মধ্য
ডান:=মধ্য - 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
