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

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

Pythonで理解する蟻本「3-1 平均最大化」(p.132)

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

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

入力


n\,k\\w_1\,v_1\\:\\w_n\,v_n

入力例



3 2
2 2
5 3
2 1


解答

INF = 10 ** 6 + 1

# 入力
n, k = map(int,input().split())
w = [None] * n
v = [None] * n
for i in range(n):
    w[i], v[i] = map(int,input().split())

y = [None] * n    # v - x * w

# 条件を満たすか判定
def C(x):
    for i in range(n):
        y[i] = v[i] - x * w[i]
    y.sort()
    
    # yの大きいほうからk個の和を計算
    sum = 0
    for i in range(k):
        sum += y[n - i - 1]
    
    return sum >= 0

lb = 0
ub = INF
for i in range(100):
    mid = (lb + ub) / 2
    if C(mid):
        lb = mid
    else:
        ub = mid
    
print(ub)