Pythonで同じ長さのk個のリボンの最大長を見つけるプログラム

リボンの長さを表す正の数のリストがあり、1つの値kもあるとします。リボンは何度でもカットできます。長さrのリボンをk個持つことができるように、最大​​の長さrを見つける必要があります。そのような解決策が見つからない場合は、-1を返します。

したがって、入力がribbons =[1、2、5、7、15] k =5の場合、サイズ15のリボンをそれぞれ長さ5の3つの部分にカットできるため、出力は5になります。次に、サイズ7のリボンをサイズ2と5にカットします。また、サイズ5のリボンがもう1つあるので、合計でサイズ5のリボンが5つ得られます。

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

• 左：=0
• 右：=リボンの最大数
• 左<右、実行
  • mid：=フロア（左+右+ 1）/ 2
  • （少なくともkであるリボン内の各ribbonLenのribbonLenのフロア/ mid）を含むリストに存在するすべての要素の合計の場合、
    • 左：=中央
  • それ以外の場合、
    • 右：=半ば-1
• 左がゼロ以外の場合、
  • 左に戻る
• 戻り値-1

例

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

def solve(ribbons, k):
   left = 0
   right = max(ribbons)
   while left < right:
      mid = (left + right + 1) // 2
      if sum((ribbonLen // mid for ribbonLen in ribbons)) >= k:
         left = mid
      else:
         right = mid - 1
   if left:
      return left
   return -1

ribbons = [1, 2, 5, 7, 15]
k = 5
print(solve(ribbons, k))

入力

[1, 2, 5, 7, 15], 5

出力

5