Pythonでバッグ内のボールの最小制限を見つけるプログラム

配列numsがあり、i番目の要素がnums[i]個のボールを含むバッグを示しているとします。 mxという別の値もあります。最大mx回で次の操作を実行できます-

• ボールのバッグを選択し、少なくとも1つのボールが入った2つの新しいバッグに分割します。

• ここでのペナルティは、バッグ内のボールの最大数です。

手術後のペナルティを最小限に抑える必要があります。したがって、最後に、操作を実行した後、可能な限り最小限のペナルティを見つける必要があります。

したがって、入力がnums =[4,8,16,4]、mx =4の場合、次の操作を実行できるため、出力は4になります。最初は[4,8,16,4]のようなバッグがあります。 、[4,8,8,8,4]のように16個のボールが付いたバッグを分割し、次に8個のボールが付いたバッグごとに4個のボールが付いた2個のバッグに分割すると、配列は[4,4,4、 8,8,4]、次に[4,4,4,4,4,8,4]、最後に[4,4,4,4,4,4,4,4]なので、ここでは最小で4つのボールがあります、それがペナルティです。

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

• 関数helper（）を定義します。これはターゲットを取ります、mx

• ターゲットが0と同じ場合、

  • mx+1を返す

• カウント：=0

• numsのnumごとに、実行します

  • count：=count +（num-1）/targetの商

• リターンカウント<=mx

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

• left：=（numsのすべての要素の合計/（numsのサイズ+ mx））と1の商の最大値

• 右：=最大数

• 左<右、する

  • mid：=（左+右）/2の商

  • helper（mid、mx）がゼロ以外の場合、

    • 右：=半ば

  • それ以外の場合

    • 左：=半ば+ 1

• 左に戻る

例

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

def helper(target, mx):
   if target == 0:
      return mx + 1
   count = 0
   for num in nums:
      count += (num - 1) // target
   return count <= mx

def solve(nums, mx):
   left, right = max(sum(nums) // (len(nums) + mx), 1), max(nums)
   while left < right:
      mid = (left + right) // 2
      if helper(mid, mx):
         right = mid
      else:
         left = mid + 1
   return left

nums = [4,8,16,4]
mx = 4
print(solve(nums, mx))

入力

[4,8,16,4], 4

出力

4