如上,我也不知道为什么模拟退火会恒WA几个点,求调
//【模板】模拟退火
#include<bits/stdc++.h>
#define MAXN 15
using namespace std;
inline void read(int &n){
int s=0,t=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-') t=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
s=(s<<3)+(s<<1)+(c^48);c=getchar();
}
n=s*t;
}
inline void put(int n){
if(n<0){
putchar('-');n=-n;
}
if(n<10){
putchar(n+48);return;
}
put(n/10);
putchar(n%10+48);
}
int n;
double answ,pos[MAXN][MAXN],ans[MAXN],dans[MAXN],dis[MAXN];
inline double calc(double a[]){
double res=0,sum=0;
for(register int i=0;i<=n;++i){
dis[i]=0;
for(register int j=1;j<=n;++j){
double dpos=pos[i][j]-a[j];
dis[i]+=dpos*dpos;
}
//dis[i]=sqrt(dis[i]);
//这里也是不知道为什么,本来求距离要开平方,但是开平方后会跳到一个绝对值极其巨大且复杂的数上,有没有奆佬能解释一下
sum+=dis[i];
}
sum/=(n+1);
for(register int i=0;i<=n;++i){
double dpos=(sum-dis[i]);
res+=dpos*dpos;
}
res/=(n+1);res=sqrt(res);
return res;
}
inline void SA(){
for(register double t=3000;t>1e-15;t*=0.995){
for(register int i=1;i<=n;++i) dans[i]=ans[i]+(rand()*2-RAND_MAX)*t;
double dw=calc(dans),d=dw-answ;
if(d<0){
for(register int i=1;i<=n;++i) ans[i]=dans[i];
answ=dw;
}
else if(exp(-d/t)*RAND_MAX>rand()){
for(register int i=1;i<=n;++i) ans[i]=dans[i];
answ=dw;
}
}
}
int main(){
srand(time(NULL));
read(n);
for(register int i=0;i<=n;++i)
for(register int j=1;j<=n;++j){
scanf("%lf",&pos[i][j]);ans[j]+=pos[i][j];
}
for(register int i=1;i<=n;++i) ans[i]/=(n+1);
answ=calc(ans);
SA();SA();SA();SA();
for(register int i=1;i<=n;++i) printf("%.3lf ",ans[i]);
putchar('\n');
return 0;
}