P15077 [ICPC 2024 Chengdu R] Double 11

随着双十一购物节临近，一家商店正在为活动筹备其畅销商品。 共有 $n$ 种畅销商品，每种商品的日销售量为 $s_i$。商品需要多次补货以满足销售需求，并且由于仓库空间有限，总库存不得超过存储容量。 如果每次只补货一种商品，工作量会过于繁重。为了优化补货流程，商店决定将这 $n$ 种商品划分为 $m$ 个组，并为每个组分配一个补货参数。对于第 $j$ 组，其补货参数 $k_j$ 是一个正实数，这意味着对于该组中的每种商品 $i$，每次补货将准备 $k_j \cdot s_i$ 的货量，并且平均每天将补货 $\frac{1}{k_j}$ 次。注意，$k_j$ 可以大于、小于或等于 $1$。 令 $c_i$ 表示商品 $i$ 所属的组别索引。仓库中的最大库存量可以表示为 $\sum_{i=1}^{n}{k_{c_i} \cdot s_i}$。由于仓库容量限制，该值不能超过 $1$。 你的任务是找到一个方案，将 $n$ 种商品划分为 $m$ 个组，并为每个组分配一个补货参数，使得在满足仓库容量限制（即 $\sum_{i=1}^{n}{k_{c_i} \cdot s_i} \le 1$）的前提下，最小化每日的总补货次数 $\sum_{i=1}^n{\frac{1}{k_{c_i}}}$。为方便起见，你需要输出最小答案的平方根，即 $\sqrt{\sum_{i=1}^n{\frac{1}{k_{c_i}}}}$。注意，不同的组可以分配相同的补货参数。

- 第一行包含两个整数 $n$ 和 $m$（$1 \le m \le n \le 2 \cdot 10^5$），分别表示商品种类数和组数。 - 第二行包含 $n$ 个整数 $s_i$（$1\le s_i \le 10^5$），表示第 $i$ 种商品的销售量。

输出一个实数，表示答案。当你的输出的相对误差或绝对误差不超过 $10^{-9}$ 时，即被视为正确。

对于第一个示例，设 $k_1=\frac{1}{3+\sqrt{21}}, k_2=\frac{1}{7+\sqrt{21}}$，且 $c_1=c_2=1, c_3=c_4=2$。则最大库存为 $(1+2)k_1 + (3+4)k_2 = 1$，总补货次数为 $\frac{2}{k_1}+\frac{2}{k_2}=20+4\sqrt{21}$。因此，答案为 $\sqrt{20+4\sqrt{21}} \approx 6.1911471295571$，这是最小值。 翻译由 DeepSeek V3 完成