「BZOJ2428」[HAOI2006] 均分数据

2014年12月2日3,7024

Description

已知N个正整数:A1、A2、……、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

题解

我乱写了个模拟退火TAT

 

说点什么

提醒
avatar
XXXXXX
XXXXXX

我怎么觉得这个是爬山啊。。。 /14
为什么是rand()%10000>T&&ans>pre 这样的话,可能更优解不都选不了吗QAQ
所以不应该是rand()%10000>T||ans>pre吗
Orz

Name :Ivan
Name :Ivan

为什么要交换??swap(a[i],a[rand()%i+1]);

steven
steven

然而为何现在过不了。。。

小小泥娃_

模拟退火…