3925: 01 分数规划
内存限制：256 MB
时间限制：1.500 S
评测方式：文本比较
命题人：
提交：0
解决：0
题目描述
这是一道模板题。
给你 $n$ 个物品，每个物品有两个属性 $a_i$ 和 $b_i$，求一组解 $x_i(1\le i\le n, x_i=0$ 或 $1)$ 使
$$\large\frac{\Sigma_{i=1}^{n}a_i\times x_i}{\Sigma_{i=1}^{n}b_i\times x_i}$$
最大，且恰好有 $k$ 个 $x_i$ 为 $1$。
请求出这个最大值。
输入
第一行两个数，$n,k$。
第二行 $n$ 个数，依次表示 $a_1,a_2\dots a_n$。
第三行 $n$ 个数，依次表示 $b_1,b_2\dots b_n$。
输出
一行，一个实数，精确到小数点后 $4$ 位。
样例输入 复制
5 3
1 2 4 1 2
4 3 9 3 7样例输出 复制
0.4667提示
输入样例2
3 2 5 0 2 5 1 6
输出样例2
0.8333
输入样例3
10 6 1 5 3 7 2 8 5 4 2 6 15 35 12 12 9 15 7 7 13 15
输出样例3
0.4923
数据范围：$ 1 \leq k \leq n \leq 10^5, $ $ 1 \leq a_i \leq b_i \leq 10^6 $.