手伝いとお小遣い

2 secs 1024 MB

問題

子供が家で家事を手伝いたいと思っています。家事は $N$ 種類あり、各家事 $i$ には労力 $E_i$ と報酬としてもらえるお小遣い $P_i$ が定められています。子供は正確に $K$ 個の家事を選んで手伝うことにしました。

子供の目的は、選んだ $K$ 個の家事の労力の総和とお小遣いの総和の比率、 $\displaystyle\frac{\sum P_i}{\sum E_i}$ を最大化することです。この最大値を求めてください。

N K
E_1 E_2 ... E_N
P_1 P_2 ... P_N

最大値を出力してください。相対誤差が $10^{-5}$ 以下または絶対誤差が $10^{-5}$ 以下であれば正解として扱われる。

4 3
2 4 6 7
3 4 1 4

0.846153846154

1,2,4番目の手伝いを選ぶと、 $\displaystyle\frac{3 + 4 + 4}{2 + 4 + 7} = 0.84615384615...$ となりこれが最適です。

7 3
10 93 19 48 50 29 42
14 58 24 27 83 29 88

1.813725490196

登録なしで提出できます。

Go (1.21)