#P2503. [HAOI2006] 均分数据

    ID: 1511 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>模拟贪心2006河南各省省选模拟退火

[HAOI2006] 均分数据

题目描述

已知 nn 个正整数 a1,a2...ana_1,a_2 ... a_n 。今要将它们分成 mm 组,使得各组数据的数值和最平均,即各组数字之和的均方差最小。均方差公式如下:

$$\sigma = \sqrt{\frac 1m \sum\limits_{i=1}^m(\overline x - x_i)^2},\overline x = \frac 1m \sum\limits_{i=1}^m x_i $$

其中 σ\sigma 为均方差,xˉ\bar{x} 为各组数据和的平均值,xix_i 为第 ii 组数据的数值和。

输入格式

第一行是两个整数,表示 n,mn,m 的值( nn 是整数个数,mm 是要分成的组数)

第二行有 nn 个整数,表示 a1,a2...ana_1,a_2 ... a_n。整数的范围是 [1,50][1,50]

(同一行的整数间用空格分开)

输出格式

输出一行一个实数,表示最小均方差的值(保留小数点后两位数字)。

6 3
1 2 3 4 5 6

0.00

提示

样例解释:1,61,62,52,53,43,4 分别为一组

【数据规模】

对于 40%40\% 的数据,保证有 mn10m \le n \le 102m62 \le m \le 6

对于 100%100\% 的数据,保证有 mn20m \le n \le 202m62 \le m \le 6