题目描述
已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：
输入输出格式
输入格式：
输入文件data.in包括：
第一行是两个整数，表示N,M的值（N是整数个数，M是要分成的组数）
第二行有N个整数，表示A1、A2、……、An。整数的范围是1--50。
（同一行的整数间用空格分开）
输出格式：
输出文件data.out包括一行，这一行只包含一个数，表示最小均方差的值(保留小数点后两位数字)。
输入输出样例
说明
样例解释：1和6、2和5、3和4分别为一组
【数据规模】
对于40%的数据，保证有K<=N <= 10，2<=K<=6
对于全部的数据，保证有K<=N <= 20，2<=K<=6
直接强上模拟退火
随机出每个位置在哪个地方
然后每次任意取出一个元素，加到最小的分组中
exp的设定就按套路来，用更新后的值减去之前的值
然后在BZOJ上T飞了
// luogu-judger-enable-o2
#include<cstdio>
#include<cmath>
#include<ctime>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#define sqr(x) ((x)*(x))
const int MAXN = ;
const double eps = 1e-;
const int INF = 1e9 + ;
using namespace std;
inline int read() {
char c = getchar();int x = , f = ;
while(c < '' || c > '') {if(c == '-') f = -;c = getchar();}
while(c >= '' && c <= '') {x = x * + c - '';c = getchar();}
return x * f;
}
int N, M;
int belong[MAXN], a[MAXN];
double sum[MAXN], Aver = , Best = 1e20;
void MoNiTuiHuo() {
memset(sum, , sizeof(sum));
const double DeltaT = 0.99;
double ans = ;
for(int i = ; i <= N; i++) belong[i] = rand() % M + , sum[ belong[i] ] += a[i];
for(int i = ; i <= M; i++) ans += sqr(sum[i] - Aver);
for(double T = ; T > eps; T *= DeltaT) {
int P = min_element(sum + , sum + M + ) - sum;//找出最小的位置
int X = rand() % N + ;//这里直接随机就可以
double Pre = ans;
ans -= sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver);
sum[ belong[X] ] -= a[X]; sum[P] += a[X];
ans += sqr(sum[ belong[X] ] - Aver) + sqr(sum[P] - Aver);
if((ans < Pre) || (exp( (ans-Pre)/T ) * RAND_MAX < rand() )) belong[X] = P;//以一定概率接受最优解
else ans = Pre, sum[ belong[X] ] += a[X], sum[P] -= a[X]; //不更新
}
if(ans < Best)
Best = ans;
}
int main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
#endif
srand();
N = read(); M = read();
for(int i = ; i <= N; i++) a[i] = read(), Aver += a[i];
Aver /= M;
for(int i = ; i <= ; i++) MoNiTuiHuo();
printf("%.2lf",sqrt(Best / M));//因为y=sqrt(x)这个函数具有单调性，所以最后在开根就可以
return ;
}