# BZOJ2428: [HAOI2006]均分数据

BZOJ2428: [HAOI2006]均分数据

（同一行的整数间用空格分开）

6 3
1 2 3 4 5 6

0.00

## HINT

```#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#define MAXN 25
using namespace std;
int n,m;
int belong[MAXN];
double average=0.00,minn=2147483645,val[MAXN],s[MAXN];
int date=0,w=1;char c=0;
while(c<‘0‘||c>‘9‘){if(c==‘-‘)w=-1;c=getchar();}
while(c>=‘0‘&&c<=‘9‘){date=date*10+c-‘0‘;c=getchar();}
return date*w;
}
void SA(){
double T=10000,ans=0.00;
memset(s,0,sizeof(s));
for(int i=1;i<=n;i++){
belong[i]=rand()%m+1;
s[belong[i]]+=val[i];
}
for(int i=1;i<=m;i++)ans+=(s[i]-average)*(s[i]-average);
while(T>1e-4){
double last=ans;
int x=min_element(s+1,s+m+1)-s,y=rand()%n+1;
ans-=(s[belong[y]]-average)*(s[belong[y]]-average)+(s[x]-average)*(s[x]-average);
s[belong[y]]-=val[y];s[x]+=val[y];
ans+=(s[belong[y]]-average)*(s[belong[y]]-average)+(s[x]-average)*(s[x]-average);
if(ans<last||exp((ans-last)/T)*RAND_MAX<rand())belong[y]=x;
else{
ans=last;
s[belong[y]]+=val[y];s[x]-=val[y];
}
T*=0.95;
}
minn=min(minn,ans);
}
void work(){
for(int cases=1;cases<=5000;cases++)SA();
printf("%.2lf\n",sqrt(minn/(double)m));
}
void init(){
srand(2002);
for(int i=1;i<=n;i++){
average+=val[i];
}
average/=(double)m;
}
int main(){
init();
work();
return 0;
}
```

BZOJ2428: [HAOI2006]均分数据

(0)
(0)

0条