Pythonで正確にk回のジャンプで最後の島に到達するために必要なジャンプの最大長の最小値を見つけます

数の配列Aがあるとします。Aでは、i番目の数は島が存在する位置であり、別の整数kが与えられます（1≤k

したがって、入力がA =[7、20、41、48]、k =2の場合、最後の島7〜20〜48、ここでは最大距離に到達する2つの方法があるため、出力は28になります。任意の2つの連続する島の間は48から20の間、つまり28です。ここで7から41から48までは、任意の2つの連続する島の間の最大距離は41から7の間、つまり34です。したがって、28と34の最小値は28です。

これを解決するには、次の手順に従います-

• 関数isPossible（）を定義します。これにはarr、dist、kが必要です

• n：=arrのサイズ

• req：=0

• 現在：=0

• 前：=0

• 0からnの範囲のiの場合、実行

  • currentはnと同じではありませんが（arr [current] --arr [previous]）<=dist、do

    • current：=current + 1

  • req：=req + 1

  • 電流がnと同じ場合、

    • ループから出てきます

  • 前：=現在-1

• 電流がnと同じでない場合、

  • Falseを返す

• req <=kの場合、

  • Trueを返す

• Falseを返す

• メインの方法から、次のようにします-

• n：=arrのサイズ

• 左：=0

• 右：=arrの最後の要素

• ans：=0

• 左-=右の間、実行

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

  • isPossible（arr、mid、k）がゼロ以外の場合、

    • ans：=mid

    • 右：=半ば-1

  • それ以外の場合

    • 左：=半ば+ 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