2428: [HAOI2006]均分資料
模拟退火就可以了。
選擇 a i a_i ai應該放在的位置，然後退火判斷一下。
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
const double _T=0.1,EXP_T=0.99,deta=0.0001;
int n,K,a[25],in[25],Sum[25];double x_,T,Ans;
double sqr(double x){return x*x;}
double Fire(){
double ret=0;T=10000;
for(int i=1;i<=K;i++) Sum[i]=0;
for(int i=1;i<=n;i++) in[i]=rand()%K+1,Sum[in[i]]+=a[i];
for(int i=1;i<=K;i++) ret+=(Sum[i]-x_)*(Sum[i]-x_);
while(T>_T){
int x=rand()%n+1,i=rand()%K+1;
if(T>1e3){
int MINID=1;
for(int i=2;i<=K;i++) if(Sum[MINID]>Sum[i]) MINID=i;
i=MINID;
}
double Now=0;int lst=in[x];
Now=ret-sqr(Sum[in[x]]-x_)+sqr(Sum[in[x]]-a[x]-x_)-sqr(Sum[i]-x_)+sqr(Sum[i]+a[x]-x_);
if(Now<ret||exp((ret-Now)/(deta*T))>1.0*rand()/32767) ret=Now,Sum[in[x]]-=a[x],Sum[i]+=a[x],in[x]=i;
T*=EXP_T;
}
return ret;
}
int main(){
srand(time(0));scanf("%d%d",&n,&K);
for(int i=1;i<=n;i++) scanf("%d",&a[i]),x_+=a[i];
x_/=K;Ans=Fire();
for(int i=1;i<=1000;i++) Ans=std::min(Ans,Fire());
printf("%.2lf\n",sqrt(Ans/K));
return 0;
}