演習課題「整数での二分探索」
整数n,kと長さnの配列aが与えられるので、a[0]~a[n-1]の長さのパイプからk本以上切り出すことができる整数単位での最大の長さを求めてください。
すでに入力を行うコードが実装されているので、コードを書き足して完成させてください。
期待する出力値
2
＃04:最大値を求める
このチャプターでは、レベルアップ問題集「二分探索メニュー」の「パイプを切り出そう」の問題を解いていきます。
今回の問題で求められている精度は10^{-6}(0.000001)です。また、二分探索の初期範囲は0.0から10001.0です。
したがって、二分探索で狭めるべき範囲の大きさは約10^{10}(≒10001.0/10^{-6})分の1になります。
これに対し底を2とする対数をとると、log_2(10^{10})≒33.22となります。したがって、二分探索のループの回数は34回以上にすることで必要な精度を得ることができます。
n, k = map(int, input().split())
a = [int(x) for x in input().split()]
# 変数left,rightをそれぞれ0と10001で初期化
left, right = 0, 10001
# 50回繰り返すループを作成
for _ in range(50):
# 変数midに(left+right)/2を代入
mid = (left + right) / 2
# 切り出せる本数を表す変数numを0で初期化
num = 0
# iを0からn-1まで繰り返す
for i in range(n):
# numにa[i]/midの整数部分を足す
num += int(a[i] // mid)
# もしnumがk以上なら
if num >= k:
# leftをmidで更新
left = mid
# そうでなければ
else:
# rightをmidで更新
right = mid
# leftを出力
print(left)
3 3
1 2 4
3 4
1 2 4