P15077 [ICPC 2024 Chengdu R] Double 11

With the Double 11 Shopping Festival approaching, a store is managing its best-selling products for the event. There are $n$ types of best-selling products, and the daily sales volume for each type is $s_i$. Products need to be replenished multiple times to meet sales demand, and due to limited warehouse space, the total inventory must not exceed the storage capacity. If only one type of product is replenished at a time, the workload becomes too high. To optimize replenishment, the store decides to divide the product types into $m$ groups, assigning a replenishment parameter to each group. For group $j$, the replenishment parameter $k_j$ is a positive real number, which means for each product type $i$ in this group, a volume of $k_j \cdot s_i$ will be prepared for each replenishment, and it will be replenished $\frac{1}{k_j}$ times per day on average. Note that $k_j$ can be either greater than, less than or equal to $1$. Let $c_i$ be the group index of product type $i$. The maximum inventory in the warehouse can be represented by $\sum_{i=1}^{n}{k_{c_i} \cdot s_i}$. Due to the warehouse capacity limitation, this value cannot exceed $1$. Your task is to find a scheme that divides the $n$ product types into $m$ groups and assigns a replenishment parameter to each group such that the total number of replenishments per day is minimized while satisfying the warehouse capacity limitation, i.e., minimize $\sum_{i=1}^n{\frac{1}{k_{c_i}}}$, subject to $\sum_{i=1}^{n}{k_{c_i} \cdot s_i} \le 1$. For convenience, you should output the square root of the minimal answer, i.e., $\sqrt{\sum_{i=1}^n{\frac{1}{k_{c_i}}}}$. Note that you can assign the same replenishment parameters to different groups.

The first line contains two integers $n$ and $m$ ($1 \le m \le n \le 2 \cdot 10^5$), indicating the number of product types and the number of groups. The second line contains $n$ integers $s_i$ ($1\le s_i \le 10^5$), indicating the sales volume of product type $i$.

Output one real number, indicating the answer. Your output will be considered correct if the relative or absolute error does not exceed $10^{-9}$.

For the first example, let $k_1=\frac{1}{3+\sqrt{21}}, k_2=\frac{1}{7+\sqrt{21}}$, and $c_1=c_2=1,c_3=c_4=2$. We will get the maximum inventory as $(1+2)k_1 + (3+4)k_2 = 1$, and the total number of replenishments is $\frac{2}{k_1}+\frac{2}{k_2}=20+4\sqrt{21}$. Therefore, the answer is $\sqrt{20+4\sqrt{21}} \approx 6.1911471295571$, which is the minimum.