UVA1456 Cellular Network

手机在蜂窝网络的定位是一个基本问题。假设蜂窝网络已经得知手机处于 $c_1, c_2,c_3,……,c_n$ 这 $n$ 个区域中的一个，最简单的方法是同时在这些区域中寻找手机，但这样很浪费带宽。由于蜂窝网络可以得知手机在不同区域内出现的概率，因此一个折中的方案是把这些区域分成 $w$ 组，然后一次访问。比如，一直手机可能位于 $5$ 个区域中，概率分别为 $0.3,0.05,0.1,0.3,0.25$，则一种方法是先同时访问 $\{c_1,c_2,c_3\}$，再同时访问 $\{c_4,c_5\}$，访问区域数量的期望为 $3 \times (0.3 + 0.05 + 0.1) + (3 + 2) \times (0.3 + 0.25) = 4.1$。而另一种方法是先同时访问 $\{c_1,c_4\}$，再访问 $\{c_2,c_3,c_5\}$，访问区域数量的期望为 $2 \times (0.3 + 0.3) + (3 + 2) \times (0.05 + 0.1 + 0.25) = 3.2$。你的任务是求出访问区域数量的期望的最小值。

第一行为一个整数 $T$，表示数据组数。 每组数据第一行为两个整数 $n,w​$。含义如题面所述。 每组数据第二行为 $n$ 个正整数 $u_1,u_2,u_3,……,u_n$。手机再区域 $c_i$ 的概率 $p_i = \frac{u_i}{\sum\limits_{j = 1}^n u_j}$。

对于每组数据，输出访问区域数量的期望的最小值。 ### 输入样例 ``` 2 5 2 30 5 10 30 25 5 5 30 5 10 30 25 ``` ### 输出样例 ``` 3.2000 2.3000 ```