OI题库

【问题描述】

    已知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