学步园

http://www.lydsy.com/JudgeOnline/problem.php?id=2428

我xxxxxx，运气太好了吧这都能wa。。。。。

srand一下就A了

蒟蒻想问一下，难道生成数据也会用模拟退火嘛。。。？

先把问题转化一下，就是求每组的和的平方的和最小

开始以为是状压DP，发现只有40分。。。

然后冥思苦想，最后看题解，惊呆了——模拟退火

不会调参数，所以各项参数参照hzwer

//#define _TEST _TEST
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;
/************************************************
Code By willinglive    Blog:http://willinglive.cf
************************************************/
#define rep(i,l,r) for(int i=(l),___t=(r);i<=___t;i++)
#define per(i,r,l) for(int i=(r),___t=(l);i>=___t;i--)
#define MS(arr,x) memset(arr,x,sizeof(arr))
#define LL long long
#define INE(i,u,e) for(int i=head[u];~i;i=e[i].next)
inline const int read()
{int r=0,k=1;char c=getchar();for(;c<'0'||c>'9';c=getchar())if(c=='-')k=-1;
for(;c>='0'&&c<='9';c=getchar())r=r*10+c-'0';return k*r;}
/////////////////////////////////////////////////
int n,m;
int a[22],sum;
double ave=0;
int pos[22],s[22];
/////////////////////////////////////////////////
double cal()
{
	double res=0;
	MS(s,0);
	rep(i,1,n) pos[i]=rand()%m+1;
	rep(i,1,n) s[pos[i]]+=a[i];
	rep(i,1,m) res+=s[i]*s[i];
	double T=10000;
	while(T>0.1)
	{
		T*=0.9;
		int x=rand()%n+1;
		int u=pos[x],v;
		if(T>500) v=min_element(&s[1],&s[m+1])-s;
		else v=rand()%m+1;
		if(u==v) continue;
		double pre=res;
		res-=s[u]*s[u]; res-=s[v]*s[v];
		s[u]-=a[x]; s[v]+=a[x];
		res+=s[u]*s[u]; res+=s[v]*s[v];
		if(rand()%10000>T && res>pre)
		{
			s[u]+=a[x]; s[v]-=a[x];
			res=pre;
		}
		else pos[x]=v;
	}
	return res;
}
/////////////////////////////////////////////////
void input()
{
	srand(13131);
    n=read(); m=read();
    rep(i,1,n)
    {
    	a[i]=read();
    	ave+=a[i]; sum+=a[i];
		swap(a[i],a[rand()%i+1]);
    }
    ave/=m;
}
void solve()
{
	double ans=1e10;
	rep(i,1,10000)
	{
		ans=min(ans,cal());
	}
	printf("%.2lf",sqrt((ans-2*ave*sum+m*ave*ave)/m));
}
/////////////////////////////////////////////////
int main()
{
    #ifndef _TEST
    freopen("std.in","r",stdin); freopen("std.out","w",stdout);
    #endif
    input(),solve();
    return 0;
}