怎么说呢……模拟退火是很有趣的一类题目。

这道题结合了模拟退火和贪心。

有一种假的贪心方法：对这个数组扫过去，每个数放到当前和最小的一组里面。

对于这种贪心方法，我发现，用来做模拟退火的估价函数很合适！

就是这个伢子：

double ask()
{
	int q[25]={0},i,j,w,mn;
	double sum=0;
	for(i=0;i<n;i++)
	{
		mn=1e9;
		for(j=0;j<m;j++)
			if(q[j]<mn)
				mn=q[j],w=j;
		q[w]+=a[i];
	}
	for(i=0;i<m;i++)
		sum+=(xx-q[i])*(xx-q[i]);
	return sqrt(sum/m);
}

M_sea 姐姐用的是随机贪心，就是每次随机打乱数组。用模拟退火珂能比随机打乱好些。

直接从 P3878 [TJOI2010]分金币 改过来的……几乎没调参

唯一要说的，就是最后一个点不太友好，执行 $1000$ 次 SA 不一定能过。

所以，珂以卡时限。

因为%你退火运行越多次，得出正确解的概率越高，运行时常也越长。所以让程序压着时限过就行。

就可以用这个卡时间神器：

while(clock()<900000)
	SA();

这样可以让程序运行到大约 $900$ms 的时候结束。至于为什么是 $900000$ 而不是 $900$ 还有待考究。在洛谷上让时间 $\times 1000$（ms）就行。

UPD：当天：https://www.luogu.com.cn/discuss/show/213037

linux下1000000为1s——@AK新手村

感谢神仙@AK新手村

同时可以使用 CLOCKS_PER_SEC。同样是 $1s$。

#include<bits/stdc++.h>
using namespace std;
int a[25];
int n,m;
double mn=1e9,xx;
const double o=0.95,e=1e-8;
double ask()
{
	int q[25]={0},i,j,w,mn;
	double sum=0;
	for(i=0;i<n;i++)
	{
		mn=1e9;
		for(j=0;j<m;j++)
			if(q[j]<mn)
				mn=q[j],w=j;
		q[w]+=a[i];
	}
	for(i=0;i<m;i++)
		sum+=(xx-q[i])*(xx-q[i]);
	return sqrt(sum/m);
}
void SA()
{
	double s=3000,ans;
	int w1,w2;
	for(;s>e;s*=o)
	{
		w1=rand()%n,w2=rand()%n;
		swap(a[w1],a[w2]);
		ans=ask();
		if(ans<mn)
			mn=ans;
		else if(exp((ans-mn)/s)*RAND_MAX<rand())
			swap(a[w1],a[w2]);
	}
}
int main()
{
	srand(time(0));
	int i;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		xx+=a[i];
	}
	xx/=m;
	while(clock()<900000)
		SA();
	printf("%.2f",mn);
} 

改完之后一遍稳过。

更新后的代码：

#include<bits/stdc++.h>
using namespace std;
int a[25];
int n,m;
double mn=1e9,xx;
const double o=0.95,e=1e-8;
double ask()
{
	int q[25]={0},i,j,w,mn;
	double sum=0;
	for(i=0;i<n;i++)
	{
		mn=1e9;
		for(j=0;j<m;j++)
			if(q[j]<mn)
				mn=q[j],w=j;
		q[w]+=a[i];
	}
	for(i=0;i<m;i++)
		sum+=(xx-q[i])*(xx-q[i]);
	return sqrt(sum/m);
}
void SA()
{
	double s=3000,ans;
	int w1,w2;
	for(;s>e;s*=o)
	{
		w1=rand()%n,w2=rand()%n;
		swap(a[w1],a[w2]);
		ans=ask();
		if(ans<mn)
			mn=ans;
		else if(exp((ans-mn)/s)*RAND_MAX<rand())
			swap(a[w1],a[w2]);
	}
}
int main()
{
	srand(time(0));
	int i;
	cin>>n>>m;
	for(i=0;i<n;i++)
	{
		cin>>a[i];
		xx+=a[i];
	}
	xx/=m;
	while(clock()<CLOCKS_PER_SEC*0.9)
		SA();
	printf("%.2f",mn);
}