演習課題「太巻きを分けよう（おなかいっぱい）」
整数l,n,kと長さkの配列aが与えられるので、各iについて左端からa[i]cmのところに切れ目の入った長さlcmの太巻きを切れ目に沿ってn個に切り分けるとき、分けられた太巻きのうち最も長い太巻きの長さの最小値を求めてください。
すでに入力を行うコードが実装されているので、コードを書き足して完成させてください。
期待する出力値
2
＃06:最小値の最大化
このチャプターでは、レベルアップ問題集「二分探索メニュー」の「太巻きを分けよう」の問題を解いていきます。
l, n, k = map(int, input().split())
a = [int(x) for x in input().split()]
# 配列(リスト)aの末尾にlを追加
a.append(l)
# 変数left,rightをそれぞれ0とl+1で初期化
left, right = 0, l+1
# leftとrightの差が1でない間
while right - left != 1:
# 変数midに(left+right)/2を代入
mid = (left + right) // 2
# 前回の切れ目の位置を表す変数lastと切り分けた個数を表す変数countを0で初期化
last, count = 0, 0
# iを0からkまで繰り返す
for i in range(k+1):
# もしa[i]-lastがmid以上なら
if a[i] - last >= mid:
# lastにa[i]を代入し、countを1増やす
last = a[i]
count += 1
# もしcountがn以上なら
if count >= n:
# leftをmidで更新
left = mid
# そうでなければ
else:
# rightをmidで更新
right = mid
# leftを出力
print(left)
10 3 3
1 3 8