P15069 [UOI 2024 II Stage] Disco

Anton 作为一名学校教师，正在为孩子们组织一场迪斯科舞会。他的任务是挑选一份播放列表，让每个人都对庆祝活动兴奋不已。但 Anton 有一个庞大的歌曲数据库，遗憾的是，迪斯科舞会的时间有限 :(。 具体来说，数据库中有 $n$ 首歌曲。每首歌曲可以用两个整数 $t_i$ 和 $r_i$ 来描述——歌曲的时长和评分。作为一名音乐爱好者，Anton 希望**恰好**选择 $k$ 首歌曲（即不少于 $k$ 首），以最大化评分总和与时长总和的比值。 更正式地说，设 $S$ 为歌曲集合，$X \subseteq S$，$|X|=k$ 为已选入播放列表的歌曲子集。目标是最大化 $\displaystyle \frac{\sum_{i \in X} r_i}{\sum_{i \in X} t_i}$。换句话说，需要找出将在迪斯科舞会上播放的所有歌曲的 $r_i$ 之和，再找出将在迪斯科舞会上播放的所有歌曲的 $t_i$ 之和，并用前者除以后者。需要最大化这个数值。 请找出并输出可能的最大比值。

- 第一行包含两个整数 $n$、$k$（$1 \le k \le n \le 10^5$）——歌曲总数和需选入播放列表的歌曲数量。 - 第二行包含 $n$ 个整数 $r_i$（$1 \le r_i \le 10^5$）。 - 第三行包含 $n$ 个整数 $t_i$（$1 \le t_i \le 10^5$）。

输出一个数字——最大比值。 只要你的答案的绝对误差或相对误差不超过 $10^{-4}$，即被视为正确。 形式化地说，设你的答案为 $a$，标准的答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-4}$ 时，你的答案会被接受。

在第一个示例中，需要将两首歌曲加入播放列表。因此，比值为： $$\frac{1+2}{2+3}=\frac{3}{5}=0.6$$ 在第二个示例中，最好选择第三首和第五首歌曲。因此，比值为： $$\frac{3+3}{2+3}=\frac{6}{5}=1.2$$ 翻译由 DeepSeek V3 完成