Pythonを使用してバケット内のボール間の最小力を最大化するプログラム

いくつかのバケットとx個のボールが与えられたとします。ボールをバケツに入れると、その中に特殊な力が作用し、2つのボール間の最小の力を最大化する方法を見つける必要があります。位置pとqのバケット内の2つのボール間の力は|p--q|です。私たちに与えられた入力は、バケットの位置とボールの数xを含む配列です。それらの間の最小の力を見つけなければなりません。

したがって、入力がpos =[2、4、6、8、10、12]、x =3の場合、出力は4になります。

ボールは、12個のバケットの配列で指定された位置に配置できます。 3つのボールは4、8、12の位置に配置でき、それらの間のパワーは4になります。この値をこれ以上増やすことはできません。

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

• 関数ball_count（）を定義します。これにはd

  かかります

  • および：=1

  • curr：=pos [0]

  • 1からnの範囲のiの場合、実行します

    • pos [i] --curr> =dの場合、

      • ans：=ans + 1

      • curr：=pos [i]

  • ansを返す

• n：=位置のサイズ

• リストを並べ替える

• 左：=0

• 右：=pos [-1]-pos [0]

• 左<右、する

  • mid：=right-フロア値（（right-left）/ 2）

  • ball_count（mid）> =xの場合、

    • 左：=中央

  • それ以外の場合

    • 右：=半ば-1

• 左に戻る

例

理解を深めるために、次の実装を見てみましょう-

def solve(pos, x):
   n = len(pos)
   pos.sort()

   def ball_count(d):
      ans, curr = 1, pos[0]
      for i in range(1, n):
         if pos[i] - curr >= d:
            ans += 1
            curr = pos[i]
      return ans

   left, right = 0, pos[-1] - pos[0]
   while left < right:
      mid = right - (right - left) // 2
      if ball_count(mid) >= x:
         left = mid
      else:
        right = mid - 1
   return left

print(solve([2, 4, 6, 8, 10, 12], 3))

入力

[2, 4, 6, 8, 10, 12], 3

出力

4