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;
}