题目描述

有 $n$ 个物品的体积和价值分别是 $v_i$ 和 $w_i$ ，从中选出 $k$ 个物品使得单位体积的价值最大

输入格式

第一行包含 $2$ 个正整数 $n, k$ 。

第二行包含 $n$ 个用空格分割的整数，表示物品的价值 $w_i$

第二行包含 $n$ 个用空格分割的整数，表示物品的体积 $v_i$

输出一个浮点数，表示选中 $k$ 个物品的最大单位价值

注意，结果保留 $2$ 位小数。

3 2
2 3 1
2 5 2

0.75

【样例解释 1】

请思考后再点击查看提示

设 $ok(x) == true$ 表示可以选择 $k$ 个物品使得单位价值不低于 $x$
若 $x$ 满足条件 $ok(x) == true$ ，那么所有 $x' \le x$ 必然也能满足条件 $ok(x') == true$ ，符合二分搜索的条件
所以我们只需要判断 $ok(x)$ 是否可行，即：

\frac{\sum{w_i}}{\sum{v_i}} \ge x，能否成立？

在以下作业中: