第一课堂
Current course
Participants
General
Topic 2
Topic 3
Topic 4
Topic 5
Topic 6
Topic 7
Topic 8
Topic 9
Topic 10
Topic 11
Topic 12
Topic 13
Topic 14
Topic 15
Topic 16
Topic 17
Topic 18
Topic 19
Topic 20
[HAOI2006]均分数据
Grade | 0 | Open Time | Thursday, 21 February 2013, 11:02 pm |
Discount | 0.8 | Time Discount | Thursday, 28 February 2013, 11:02 pm |
Allow late | Yes | Close Time | Thursday, 28 February 2013, 11:02 pm |
Input file | data.in | Output file | data.out |
【问题描述】
已知N个正整数:A1,A2,……,An。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:


其中第一个公式是均方差,第二个公式是各组数据和的平均值,xi为第i组数据的数值和。
【输入格式】
第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)。
第二行有N个整数,表示A1,A2,……,An。整数的范围是1--50。
(同一行的整数间用空格分开)
【输出格式】
输出文件只有一行,包括一个数 ,表示最小均方差的值(保留小数点后两位数字)。
【输入样例】
6 3
1 2 3 4 5 6
【输出样例】
0.00
(1和6,2和5,3和4分别为一组)
【数据范围】
对于40%的数据,保证有M<=N<=10,2<=M<=6
对于100%的数据,保证有M<=N<=20,2<=M<=6