新知识get:模拟退火
设置一个温度T，T越小越不随机
然后做个几万遍就可以了。
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
double ans=2147483647,average=0;
int n,m,a[10005],sum[10005],zu[10005];
void Fire(){
double T=10000,nowans=0;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++){
zu[i]=rand()%m+1;
sum[zu[i]]+=a[i];
}
for(int i=1;i<=m;i++){
nowans+=(sum[i]-average)*(sum[i]-average);
}
while(T>0.1){
T*=0.9;
int Nx,Ny,R=rand()%n+1;
Nx=zu[R];
if(T>500){
int sa=2147483647,sb;
for(int i=1;i<=m;i++){
if(sa>sum[i]){
sa=sum[i];
sb=i;
}
}
Ny=sb;
}
else Ny=rand()%m+1;
if(Nx==Ny)continue;
double lastans=nowans;
nowans-=(sum[Nx]-average)*(sum[Nx]-average);
nowans-=(sum[Ny]-average)*(sum[Ny]-average);
sum[Nx]-=a[R];
sum[Ny]+=a[R];
nowans+=(sum[Nx]-average)*(sum[Nx]-average);
nowans+=(sum[Ny]-average)*(sum[Ny]-average);
if(nowans<=lastans){zu[R]=Ny;}
else {
if(rand()%10000>T){
sum[Nx]+=a[R];
sum[Ny]-=a[R];
nowans=lastans;
}
else {
zu[R]=Ny;
}
}
}
ans=min(nowans,ans);
}
int main(){
srand(19990720);
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
average+=a[i];
}
average/=m;
for(int i=1;i<=10000;i++){
Fire();
}
printf("%.2lf\n",sqrt(ans/m));
return 0;
}
评论 (0)
