演習課題「平均価値の最小値」
整数n,kと長さnの配列w,vが与えられるので、重さがw[0]からw[n-1],価値がv[0]からv[n-1]までのn個の財宝からk個の財宝を選び、価値の合計を重さの合計で割った値である平均価値を最小化してください。
答えは小数点以下を切り捨てた整数で求めてください。
すでに入力を行うコードが実装されているので、コードを書き足して完成させてください。
期待する出力値
1
＃05:平均の最大化
このチャプターでは、レベルアップ問題集「二分探索メニュー」の「効率よく盗もう」の問題を解いていきます。
n, k = map(int, input().split())
w = [int(x) for x in input().split()]
v = [int(x) for x in input().split()]
# 変数left,rightをそれぞれ0と5001で初期化
left, right = 0, 5001
# 50回繰り返すループを作成
for _ in range(50):
# 変数midに(left+right)/2を代入
mid = (left + right) / 2
# 長さnの配列(リスト)tmpを作成
tmp = [0] * n
# iを0からn-1まで繰り返す
for i in range(n):
# tmp[i]にv[i]-mid*w[i]を代入
tmp[i] = v[i] - mid * w[i]
# tmpを大きい順にソート
tmp.sort(reverse=True)
# 変数sumを0で初期化
sum = 0
# iを0からk-1まで繰り返す
for i in range(k):
# sumにtmp[i]を足す
sum += tmp[i]
# もしsumが0以上なら
if sum >= 0:
# leftをmidで更新
left = mid
# そうでなければ
else:
# rightをmidで更新
right = mid
# leftを出力
print(left)
3 2
1 2 3
3 2 1