bzoj 2428: [HAOI2006]均分数据

 #include<cstdio>
#include<iostream>
#include<cstdlib>
#include<ctime>
#include<cstring>
#include<cmath>
#include<algorithm>
#define M 100
using namespace std;
int n,m,a[M],pos[M];
double rev,sum[M],ans,mn=1e30,pre;
void solve()
{
memset(sum,,sizeof(sum));
ans=;
for(int i=;i<=n;i++)
pos[i]=rand()%m+;
for(int i=;i<=n;i++)
sum[pos[i]]+=a[i];
for(int i=;i<=m;i++)
ans+=(sum[i]-rev)*(sum[i]-rev);
double T=;
for(;T>0.1;)
{
int t1=rand()%n+,x=pos[t1],y=rand()%m+;
if(x==y)
continue;
T*=0.9;
pre=ans;
ans-=(sum[x]-rev)*(sum[x]-rev);
ans-=(sum[y]-rev)*(sum[y]-rev);
sum[x]-=a[t1];
sum[y]+=a[t1];
ans+=(sum[x]-rev)*(sum[x]-rev);
ans+=(sum[y]-rev)*(sum[y]-rev);
if(ans>pre)
{
ans=pre;
sum[x]+=a[t1];
sum[y]-=a[t1];
}
else
pos[t1]=y;
}
if(ans<mn)
mn=ans;
return;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)
{
scanf("%d",&a[i]);
rev+=a[i];
swap(a[i],a[rand()%i+]);
}
rev/=m;
for(int i=;i<=;i++)solve();
printf("%.2lf",sqrt(mn/m));
return ;
}

模拟退火 乱搞

上一篇:Gradle构建Java Web应用:Servlet依赖与Tomcat插件(转)


下一篇:MySQL之使用DDL语句创建表