F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 2428. -- [HAOI2006]均分数据

2428: [HAOI2006]均分数据

Time Limit: 5 Sec  Memory Limit: 128 MB
Submit: 3875  Solved: 1234
[Submit][Status][Discuss]

Description

已知N个正整数:A1A2、……、An 。今要将它们分成M组,使得各组数据的数值和最平均,即各组的均方差最小。均方差公式如下:

,其中σ为均方差,是各组数据和的平均值,xi为第i组数据的数值和。

 

Input

第一行是两个整数,表示N,M的值(N是整数个数,M是要分成的组数)
第二行有N个整数,表示A1、A2、……、An。整数的范围是1--50。
(同一行的整数间用空格分开)

Output

这一行只包含一个数,表示最小均方差的值(保留小数点后两位数字)

Sample Input

6 3
1 2 3 4 5 6

Sample Output

0.00

HINT

对于全部的数据,保证有K<=N <= 20,2<=K<=6

Source

Day2

[Submit][Status][Discuss]

HOME Back