#P18209. Double 11
Double 11
Double 11
双十一购物节即将到来,一家商店正在安排热销商品的补货工作。
有 种商品,第 种商品的日销量为 。为了满足销售需求,每种商品都需要多次补货;但仓库空间有限,总库存不能超过容量。
若每次只为一种商品补货,工作量会很大。商店决定把这 种商品分成 组,并为每组设置一个补货参数。第 组的参数 是一个正实数,表示这一组中的每种商品 ,每次备货量为 ,平均每天补货 次。 可以大于、等于或小于 。
设第 种商品所属的组为 。仓库的最大总库存为
该值不能超过仓库容量 。
请把所有商品分成 组,并为每组选择参数,在满足容量约束的前提下,使每天的总补货次数
最小。为了方便,输出这个最小值的平方根。不同组可以使用相同的补货参数。
输入格式
第一行包含两个整数 ,分别表示商品种类数与分组数。
第二行包含 个整数 ,表示各商品的日销量。
输出格式
输出一个实数,表示最少总补货次数的平方根。
当你的答案与正确答案的绝对误差或相对误差不超过 时,答案被认为正确。
数据范围
- ;
- 。
输入只有一组数据。
样例一
输入:
4 2
1 2 3 4
输出:
6.1911471295571
解释:令
$$k_1=\frac1{3+\sqrt{21}},\qquad k_2=\frac1{7+\sqrt{21}},$$并令 ,。此时最大库存为
总补货次数为
因此答案为 ,可以证明这是最小值。
样例二
输入:
10 3
1 2 3 4 5 6 7 8 9 10
输出:
22.5916253665141