已知N个正整数：A1、A2、……、An 。今要将它们分成M组，使得各组数据的数值和最平均，即各组的均方差最小。均方差公式如下：
这道题是模拟退火，但是这个调整的是整个序列，怎么办呢？
一看数据范围，“对于全部的数据，保证有K<=N <= 20，2<=K<=6”暴力枚举序列都不会T
其实为了让它在最少时间内出解，还要保证解的精度，贪心就很重要了（比如说来一个数就插到和最小的组里）
#include<bits/stdc++.h> using namespace std; int n; double m; double a[21],bucket[10]; int main(){ cin>>n>>m; int i,j,k; double pi=0,s=0; for(i=1;i<=n;i++)scanf("%lf",&a[i]),pi+=a[i],s+=a[i]; pi/=m; double ans=1e15; for(i=1;i<=200000;i++){ double sum=m*pi*pi-2*pi*s; random_shuffle(a+1,a+n+1); memset(bucket,0,sizeof(bucket)); for(j=1;j<=n;j++){ int p=1; for(k=2;k<=m;k++)if(bucket[p]>bucket[k])p=k; bucket[p]+=a[j]; } for(j=1;j<=m;j++)sum+=bucket[j]*bucket[j]; ans=min(ans,sum); } ans/=m; printf("%.2lf\n",sqrt(ans)); return 0; }
原文：https://www.cnblogs.com/zbsakioi/p/11032664.html