题目描述
已知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
1 2 3 4 5 6
样例输出
0.00
提示
对于全部的数据，保证有K<=N <= 20，2<=K<=6
模拟退火，每次退火先将每个数随机分组，然后在降温过程中每次将一个数的所属分组改变，当答案更优时则保存改变，但当答案变劣时也有一定几率保存改变。最后将每次退火得到的最优解取最小值即可。
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<bitset>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
double a[100];
double sum[100];
int pos[100];
double avr;
double tmpans;
double ans=0x3fffffff;
int n,m;
void SA()
{
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++)
{
pos[i]=rand()%m+1;
sum[pos[i]]+=a[i];
}
tmpans=0;
for(int i=1;i<=m;i++)
{
tmpans+=(sum[i]-avr)*(sum[i]-avr);
}
for(double T=10000;T>0.001;T*=0.98)
{
int x=rand()%n+1;
int block;
double tmp=tmpans;
if(T>500)
{
block=min_element(sum+1,sum+1+m)-sum;
}
else
{
block=rand()%m+1;
}
if(pos[x]==block)continue;
tmpans-=(sum[pos[x]]-avr)*(sum[pos[x]]-avr);
tmpans+=(sum[pos[x]]-a[x]-avr)*(sum[pos[x]]-a[x]-avr);
tmpans-=(sum[block]-avr)*(sum[block]-avr);
tmpans+=(sum[block]+a[x]-avr)*(sum[block]+a[x]-avr);
if(rand()%10000+1>T&&tmpans>tmp)
{
tmpans=tmp;
}
else
{
sum[pos[x]]-=a[x];
sum[block]+=a[x];
pos[x]=block;
}
}
ans=min(ans,tmpans);
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%lf",&a[i]);
avr+=a[i];
swap(a[i],a[rand()%i+1]);
}
avr/=(double)m;
for(int i=1;i<=6000;i++)
{
SA();
}
printf("%.2f\n",sqrt(ans/(double)m));
}