模拟退火：
模拟退火！每次随机一个位置加给sum[]最小的组。
参数真特么玄学啊。。气的不想调了（其实就是想刷刷最优解）
如果用DP去算好像更准。。
//832kb 428ms
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <assert.h>
#include <algorithm>
#define gc() getchar()
#define D (0.997)//big enough!
#define eps (1e-3)
#define Rand(x) (rand()%x+1)
const int N=22;
int n,K,A[N],sum[7],bel[N];
double Ans=1e14,Aver,Tmp;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
inline double Squ(double x){
return x*x;
}
inline void Move(int fr,int to,int tar){
sum[fr]-=A[tar], sum[bel[tar]=to]+=A[tar];
}
//inline void Update(double &x){
// x=0.0; for(int i=1; i<=K; ++i) x+=Squ(sum[i]);
//}
void SA()
{
memset(sum,0,sizeof sum);
for(int i=1; i<=n; ++i) sum[bel[i]=Rand(K)]+=A[i];
double ans=0,nxt;
for(int i=1; i<=K; ++i) ans+=Squ(sum[i]);
Ans=std::min(Ans,ans+Tmp);
for(double T=1e7/*big enough*/; T>eps; T*=D)//Times:6898
{
int tar=Rand(n), fr=bel[tar], to=std::min_element(sum+1,sum+1+K)-sum;
if(fr==to) continue;
nxt=ans-Squ(sum[fr])-Squ(sum[to]);
Move(fr,to,tar);
nxt+=Squ(sum[fr])+Squ(sum[to]);
if(nxt<ans || (exp((ans-nxt)/T)*RAND_MAX>rand())) ans=nxt;//!
else Move(to,fr,tar);
Ans=std::min(Ans,ans+Tmp);//这个放里头！
}
}
int main()
{
n=read(),K=read();
int sum=0;
for(int i=1; i<=n; ++i) sum+=(A[i]=read());
Aver=1.0*sum/K, Tmp=K*Aver*Aver-2.0*sum*Aver;
// std::random_shuffle(A+1,A+1+n);//这东西。。有时好有时坏
for(int i=1; i<=30; ++i) SA();
printf("%.2lf",sqrt(Ans/(double)K));
return 0;
}简单好写(错误率高)的裸随机化贪心：
使每组(sum_i-Average)尽量平均(也就是使Σ(sum_i^2)最小)。数据范围这么小，而且只保留两位。。
不连续分组很难办，但是random_shuffle()一下连续分组很多次就可以达到伪不连续分组的效果了。。
具体，我们可以随便分啊按照某种策略来分，比如依次分给当前sum最小的组。
被随机数种子一直卡一个点是怎样的体验。。我特么不设了。
//832kb 2448ms
#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=21;
int n,K,A[N],sum[7];
double Ans=1e15,Aver,Tmp;
inline int read()
{
int now=0;register char c=gc();
for(;!isdigit(c);c=gc());
for(;isdigit(c);now=now*10+c-'0',c=gc());
return now;
}
void Work()
{
std::random_shuffle(A+1,A+1+n);
memset(sum,0,sizeof sum);
for(int i=1; i<=n; ++i)
sum[std::min_element(sum+1,sum+1+K)-sum]+=A[i];
double res=0;
for(int i=1; i<=K; ++i) res+=1.0*sum[i]*sum[i];//Aver可以提出来。。
Ans=std::min(Ans,res+Tmp);
}
int main()
{
n=read(),K=read();
int sum=0;
for(int i=1; i<=n; ++i) sum+=(A[i]=read());
Aver=1.0*sum/K, Tmp=K*Aver*Aver-2.0*sum*Aver;
for(int i=1; i<=300000; ++i) Work();
printf("%.2lf",sqrt(Ans/(double)K));
return 0;
}BZOJ.2428.[HAOI2006]均分数据(随机化贪心/模拟退火)
原文：https://www.cnblogs.com/SovietPower/p/9172977.html