#78. 01 分数规划

01 分数规划

当前没有测试数据。

题目描述

这是一道模板题。

给你 nn 个物品,每个物品有两个属性 aia_ibib_i,求一组解 xi(1in,xi=0x_i(1\le i\le n, x_i=01)1) 使

$$\large\frac{\Sigma_{i=1}^{n}a_i\times x_i}{\Sigma_{i=1}^{n}b_i\times x_i} $$

最大,且恰好有 kkxix_i11

请求出这个最大值。

输入格式

第一行两个数,n,kn,k
第二行 nn 个数,依次表示 a1,a2ana_1,a_2\dots a_n
第三行 nn 个数,依次表示 b1,b2bnb_1,b_2\dots b_n

输出格式

一行,一个实数,精确到小数点后 44 位。

样例 1

5 3
1 2 4 1 2
4 3 9 3 7
0.4667
3 2
5 0 2
5 1 6
0.8333
10 6
1 5 3 7 2 8 5 4 2 6
15 35 12 12 9 15 7 7 13 15
0.4923

数据范围与提示

1kn105, 1 \leq k \leq n \leq 10^5, 1aibi106 1 \leq a_i \leq b_i \leq 10^6 .