クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「3-1 Cable master（POJ No.1064）」(p.129)

Pythonで理解する蟻本（プログラミングコンテストチャレンジブック）

この記事は「プログラミングコンテストチャレンジブック第2版」（蟻本）の
「3-1 Cable master（POJ No.1064）」(p.129)
のコードをPythonで書き直したものとなっています。

入力


N\,K\\L_1\,…\,L_N

入力例



4 11
8.02 7.43 4.57 5.39


解答

import math

INF = 10 ** 5 + 1

# 入力

N, K = map(int,input().split())
L = list(map(float,input().split()))

# 条件を満たすか判定
def C(x):
    num = 0
    for i in range(N):
        num += L[i] // x
    return num >= K

# 解の存在範囲を初期化
lb = 0
ub = INF

# 解の存在範囲が十分狭くなるまで繰り返す
for i in range(100):
    mid = (lb + ub) / 2
    if C(mid):
        lb = mid
    else:
        ub = mid

print(math.floor(ub * 100) / 100)