题目
题解
模拟退火,RP算法玄学骗分
循环的次数真的是......... 多算几遍答案就很稳,超时也很稳,少算几遍答案抖得辣么惊悚,却是玄学地AC了......但考试的时候这么抖的答案怎么敢交啊
T^T(非酋流下了伤心的泪水)
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#define N 10005
#define inf 1000000000
#define ll long long
using namespace std;
int n,m,a[N],gp[N];
ll sum[N];
double x_,ans;
void SA()
{
double t=100000,now=0;
memset(sum,0,sizeof(sum));
for(int i=1;i<=n;i++) gp[i]=rand()%m+1;
for(int i=1;i<=n;i++) sum[gp[i]]+=a[i];
for(int i=1;i<=m;i++) now+=(double)(sum[i]-x_)*(sum[i]-x_);
while(t>0.1)
{
t*=0.9;
int p=rand()%n+1,x=gp[p],y=-1;//rand()一个数,记录所在组
if(t>500)//找到和最小的组的位置
{
ll Min=inf;
for(int i=1;i<=m;i++)
if(sum[i]<Min) Min=sum[i],y=i;
}
else y=rand()%m+1;//直接rand()一个组
if(x==y) continue;
double nxt=now;
nxt-=((sum[x]-x_)*(sum[x]-x_)+(sum[y]-x_)*(sum[y]-x_));
sum[x]-=a[p];sum[y]+=a[p];
nxt+=((sum[x]-x_)*(sum[x]-x_)+(sum[y]-x_)*(sum[y]-x_));
if(nxt<=now||exp((now-nxt)/t)>(double)(rand()%10000)/10000.0)
{now=nxt;gp[p]=y;}
else {sum[x]+=a[p];sum[y]-=a[p];}
ans=min(ans,now);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
x_+=a[i];
}
x_/=m;ans=inf;
for(int i=1;i<=10000;i++) SA();
printf("%.2lf",sqrt(ans/m));
return 0;
}