CF633E Startup Funding

一个电子商务创业公司正在向投资者进行融资展示。他们已经运营了 $n$ 周，并且已经有了一个网站！ 对于每一周，他们知道本周的独立访客数量 $v_{i}$ 和营收 $c_{i}$。投资者评估公司在某个从第 $l$ 周到第 $r$ 周（包含）期间的潜力时，会使用最大访客数乘以 $100$ 和该期间最小营收这二者的最小值，即：  实际上，投资者并不知道如何高效地评估这家公司，他们会随机选取 $k$ 个不同的周数 $l_{i}$，并交给创业公司的管理层。对于每个 $l_{i}$，管理层应该选择一个 $r_{i} \geq l_{i}$，并报告这段时间内的最大访客数以及最小营收。 然后，投资者会计算每个区间的潜力值，并将其中的最小 $p(l_{i}, r_{i})$ 作为公司的整体评分。假设创业公司的管理者永远会为给定的 $l_{i}$ 选择最优的 $r_{i}$（即能使评分最大化的 $r_{i}$），那么最终期望的公司评分是多少？

输入的第一行包含两个整数 $n$ 和 $k$（$1 \leq k \leq n \leq 1000000$）。 第二行包含 $n$ 个整数 $v_{i}$（$1 \leq v_{i} \leq 10^{7}$）——每周的独立访客数。 第三行包含 $n$ 个整数 $c_{i}$（$1 \leq c_{i} \leq 10^{7}$）——每周的营收。

输出一个实数，表示创业公司的期望评分。你的答案如果其绝对误差或相对误差不超过 $10^{-6}$，则被认为是正确的。 即：假设你的答案为 $a$，评测系统的答案为 $b$。如果满足下式，则判为正确： 。

考虑第一个样例。 如果投资者询问 $l_{i}=1$，公司会选择 $r_{i}=1$，此时最大访客人数为 $3$，最小营收为 $300$，则潜力值为 $min(3 \cdot 100, 300) = 300$。 如果投资者询问 $l_{i}=2$，公司会选择 $r_{i}=3$，此时最大访客数为 $2$，最小营收为 $200$，则潜力值为 $min(2 \cdot 100, 200) = 200$。 如果投资者询问 $l_{i}=3$，公司会选择 $r_{i}=3$，最大访客数为 $1$，最小营收为 $300$，潜力值为 $min(1 \cdot 100, 300) = 100$。 我们需要选出大小为 $2$ 的集合并等概率取每组的最小值。所有可能的集合为：$ \{200, 300\} $、$ \{100, 300\} $、$ \{100, 200\} $，也就是投资者等概率感受到的值为：$ \{200, 100, 100\} $。因此期望值为 $ (100 + 200 + 100) / 3 = 133.(3) $。 由 ChatGPT 5 翻译