【模板】01分数规划
时间限制:C/C++/Rust/Pascal 5秒,其他语言10秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

\hspace{15pt}对于给定的 n 件物品,每件物品都有体积 w 和价值 v 两种属性。你可以选取恰好 k 件物品放入背包带走,求解单位体积的最大价值,即使得选定物品的 \frac{\sum v}{\sum w} 最大。

输入描述:

\hspace{15pt}第一行输入两个整数 n,k\left(1\leqq n,k\leqq 5 \times 10^5\right) 代表物品数量、选取数量。

\hspace{15pt}此后 n 行,第 i 行输入两个整数 w_i,v_i\left(1\leqq w_i,v_i\leqq 10^6\right) 代表第 i 件物品的体积、价值。

输出描述:

\hspace{15pt}在一行上输出一个实数,代表单位体积的最大价值。

\hspace{15pt}由于实数的计算存在误差,当误差的量级不超过 10^{-6} 时,您的答案都将被接受。具体来说,设您的答案为 a ,标准答案为 b ,当且仅当 \frac{|a-b|}{\max(1,|b|)}\leqq 10^{-6} 时,您的答案将被接受。
示例1

输入

复制
3 2
1 2
2 4
3 7

输出

复制
2.2500000000000001

说明

\hspace{15pt}在这个样例中,一共有三种选取方案:

\hspace{23pt}\bullet\,选取第一、二件物品,此时单位体积的价值为 \frac{6}{3} = \frac{2}{1} = 2

\hspace{23pt}\bullet\,选取第一、三件物品,此时单位体积的价值为 \frac{2+7}{1+3} = \frac{9}{4} = 2.25

\hspace{23pt}\bullet\,选取第二、三件物品,此时单位体积的价值为 \frac{4+7}{2+3} = \frac{11}{5} = 2.2

\hspace{15pt}显然,选取第一、三件物品是最佳方案。
示例2

输入

复制
5 4
1 1
4 5
1 4
1 9
1 9

输出

复制
5.7500000000