#P18209. Double 11

Double 11

Double 11

双十一购物节即将到来,一家商店正在安排热销商品的补货工作。

有 nn 种商品,第 ii 种商品的日销量为 sis_i。为了满足销售需求,每种商品都需要多次补货;但仓库空间有限,总库存不能超过容量。

若每次只为一种商品补货,工作量会很大。商店决定把这 nn 种商品分成 mm 组,并为每组设置一个补货参数。第 jj 组的参数 kjk_j 是一个正实数,表示这一组中的每种商品 ii,每次备货量为 kjsik_js_i,平均每天补货 1/kj1/k_j 次。kjk_j 可以大于、等于或小于 11。

设第 ii 种商品所属的组为 cic_i。仓库的最大总库存为

∑i=1nkcisi,\sum_{i=1}^n k_{c_i}s_i,

该值不能超过仓库容量 11。

请把所有商品分成 mm 组,并为每组选择参数,在满足容量约束的前提下,使每天的总补货次数

∑i=1n1kci\sum_{i=1}^n\frac1{k_{c_i}}

最小。为了方便,输出这个最小值的平方根。不同组可以使用相同的补货参数。

输入格式

第一行包含两个整数 n,mn,m,分别表示商品种类数与分组数。

第二行包含 nn 个整数 s1,s2,…,sns_1,s_2,\ldots,s_n,表示各商品的日销量。

输出格式

输出一个实数,表示最少总补货次数的平方根。

当你的答案与正确答案的绝对误差或相对误差不超过 10−910^{-9} 时,答案被认为正确。

数据范围

  • 1≤m≤n≤2×1051\le m\le n\le2\times10^5;
  • 1≤si≤1051\le s_i\le10^5。

输入只有一组数据。

样例一

输入:

4 2
1 2 3 4

输出:

6.1911471295571

解释:令

$$k_1=\frac1{3+\sqrt{21}},\qquad k_2=\frac1{7+\sqrt{21}},$$

并令 c1=c2=1c_1=c_2=1,c3=c4=2c_3=c_4=2。此时最大库存为

(1+2)k1+(3+4)k2=1,(1+2)k_1+(3+4)k_2=1,

总补货次数为

2k1+2k2=20+421.\frac2{k_1}+\frac2{k_2}=20+4\sqrt{21}.

因此答案为 20+421≈6.1911471295571\sqrt{20+4\sqrt{21}}\approx6.1911471295571,可以证明这是最小值。

样例二

输入:

10 3
1 2 3 4 5 6 7 8 9 10

输出:

22.5916253665141