PythonでK時間で石の除去率を見つけるプログラム

パイルと呼ばれる数のリストと値kがあるとします。パイル[i]は、パイルi上の石の数を表します。 1時間ごとに、任意のパイルを選択し、そのパイルからr個の石を取り除きます。石がr個未満の山を選んだ場合でも、山を片付けるのに1時間かかります。 k時間以内にすべての石を取り除くことができるように、rの最小値を見つける必要があります。

したがって、入力がパイル=[3、6、4] k =5のような場合、出力は3になります。これは、r =3ストーン/時間の場合、2時間で2番目のパイルをクリアしてから、 2時間で3番目、1時間で最初の山をクリアします。

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

• l：=1
• h：=杭の最大数
• r：=h
• 関数turns（）を定義します。これにはrがかかります
• リストに存在するすべての要素の合計を（パイル内の各bのb / rの上限）で返します
• メインの方法から、次の手順を実行します-
• l
• mid：=（l + h）/2の床
• turn（mid）> kの場合、
  • l：=mid + 1
• それ以外の場合、
  • h：=mid
  • r：=rとmidの最小値

例

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

from math import ceil
def solve(piles, k):
   l = 1
   h = max(piles)
   r = h

   def turns(r):
      return sum(ceil(b / r) for b in piles)
   while l < h:
      mid = (l + h) // 2
      if turns(mid) > k:
         l = mid + 1
      else:
         h = mid
         r = min(r, mid)
   return r

piles = [3, 6, 4]
k = 5
print(solve(piles, k))

入力

[3, 6, 4], 5

出力

3