在Python中准确地以k次跳跃找到到达最后一个岛所需的最大跳跃最小长度

假设我们有一个数字数组A，在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的大小

• 要求：= 0

• 当前：= 0

• 上一个：= 0

• 对于0到n范围内的i，执行

• 从循环中出来

• 当前：=当前+ 1

• 而当前与n不相同，并且（arr [current]-arr [上一个]）<= dist，

• 要求：=要求+ 1

• 如果电流与n相同，则

• 上一个：=当前-1

• 如果电流与n不同，则

• 返回False

• 如果req <= k，则

• 返回True

• 返回False

• 从主要方法中，执行以下操作-

• n：= arr的大小

• 左：= 0

• 右：= arr的最后一个元素

• 回答：= 0

• 当左-=右时

• 左：=中+ 1

• ans：=中

• 右：=中-1

• 中：=（左+右）/ 2;

• 如果isPossible(arr,mid,k)不为零，则

• 除此以外，

• 返回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