bzoj 2428 均分数据 模拟退火

模拟退火

按照自己的思路打了，结果WA，发现退火最关键的就是初温，降温，和修改次数，

这个题还在外层带了一个循环，骚气

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define inf 0x3f3f3f3f3f3f3f3fll

using namespace std;

double av,ans,minn=inf,sum[30];

int n,m,a[30],be[30];

double Rand(){return (rand()%1000)/1000.0;}

void work(){

	memset(sum,0,sizeof sum);

	ans=0;

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

		be[i]=rand()%m+1,sum[be[i]]+=a[i];

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

		ans+=(sum[i]-av)*(sum[i]-av);

	double t=10000;

	while(t>0.1){

		int x=rand()%n+1,y=be[x],z;

		if(t>500)z=min_element(sum+1,sum+m+1)-sum;

		else z=rand()%m+1;

		double nxt=ans;

		nxt-=(sum[y]-av)*(sum[y]-av);

		nxt-=(sum[z]-av)*(sum[z]-av);

		sum[y]-=a[x]; sum[z]+=a[x];

		nxt+=(sum[y]-av)*(sum[y]-av);

		nxt+=(sum[z]-av)*(sum[z]-av);

		double dE=ans-nxt;

		if(dE>0||exp(dE/t)>Rand())

			ans=nxt,be[x]=z;

		else

			sum[y]+=a[x],sum[z]-=a[x];

		t*=0.9;

	}

	if(ans<minn) minn=ans;

}

int main(){

	srand(20001101);

	scanf("%d%d",&n,&m);

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

		scanf("%d",&a[i]);

		av+=a[i];

	}av/=m;

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

	printf("%0.2lf\n",sqrt(minn/m));

	return 0;

}