【BZOJ2428】均分数据（模拟退火）

题面

BZOJ

题解

先说说黄学长的做法：

当温度比较高的时候，贪心

每次随机一个数，把他放进当前和最少的那一组里面

温度足够低的时候就完全随机然后转移

这样子写貌似会挂？？？

（我只有70分。。，洛谷测的）

然后看到了\(ZSY\)巨神的做法

（太强啦，实在是太强啦，强无敌呀）

对于一个排列，分组强制连续

答案显然唯一，做一遍\(dp\)就好

所以退火的时候每次交换两个位置。。。

不知道为什么这样就过了。。。

懵逼

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

#include<ctime>

using namespace std;

#define ll long long

#define RG register

#define MAX 50

#define sqr(x) ((x)*(x))

inline int read()

{

    RG int x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

int n,m;

int a[MAX],b[MAX],s[MAX];

double Rand(){return rand()%10000/10000;}

double ans=1e50,f[MAX][MAX],avg;

double Calc()

{

	memset(f,127,sizeof(f));

	for(int i=1;i<=n;++i)s[i]=s[i-1]+a[i];

	f[0][0]=0;

	for(int i=1;i<=n;++i)

		for(int j=1;j<=i;++j)

			for(int k=0;k<i;++k)

				f[i][j]=min(f[i][j],f[k][j-1]+sqr(s[i]-s[k]-avg));

	ans=min(ans,f[n][m]);

	return f[n][m];

}

void SA(double T)

{

	double now=ans;

	while(T>1e-9)

	{

		int x=rand()%n+1,y=rand()%n+1;

		if(x==y)continue;

		swap(a[x],a[y]);

		double nw=Calc();

		if(nw<now||exp((now-nw)/T)>Rand())now=nw;

		else swap(a[x],a[y]);

		T*=0.99;

	}

	for(int i=1;i<=10000;++i)

	{

		int x=rand()%n+1,y=rand()%n+1;

		swap(a[x],a[y]);Calc();

		swap(a[x],a[y]);

	}

}

int main()

{

	srand(2333);

	n=read();m=read();

	for(int i=1;i<=n;++i)avg+=1.0*(a[i]=read())/m;

	Calc();

	SA(100000);

	printf("%.2lf\n",sqrt(ans/m));

	return 0;

}