SA经计算得出时间复杂度约为

$O（times*3675000)$

#include <bits/stdc++.h>
using namespace std;

const int N=1010;
const double BT=10000;
const double ET=1e-12;
const double CT=0.995;

int n;
double answ,ansx,ansy;
int x[N],y[N],w[N];

double get(double tx,double ty){
  	double res=0,dx,dy;
  	for (int a=1;a<=n;a++){
    	dx=tx-x[a];
      	dy=ty-y[a];
      	res+=sqrt(dx*dx+dy*dy)*w[a];
  	}
	return res;
}

void solve(int times){
	while(times--){
		for(double T=BT;T>=ET;T*=CT){
			double ex=ansx+(rand()*2-RAND_MAX)*T;
			double ey=ansy+(rand()*2-RAND_MAX)*T;
			double ew=get(ex,ey);
			double de=ew-answ;
			if(de<0){
				answ=ew;
				ansx=ex;
				ansy=ey;
			}else{
				if(exp((answ-ew)/T)>(double)rand() / RAND_MAX)ansx=ex,ansy=ey;
			}T*=CT;
		}
	}
	cout<<fixed<<setprecision(3);
	cout<<ansx<<' '<<ansy;
	return;
}



int main() {
	srand(time(0));
	int times=rand()%60+40;
  //说明：若times不小于40能保证至少56pts的得分
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x[i]>>y[i]>>w[i];
		ansx+=x[i],ansy+=y[i];
	}
	ansx/=n,ansy/=n;
	answ=get(ansx,ansy);
	solve(times);
  return 0;
}

经多次提交，结果如下

• AC
• 56pts WA on #8 TLE on #4 #5 #6
• 56pts WA on #8 TLE on #4 #5 #6
• 89pts WA on #5
• 89pts WA on #4
• 78pts WA on #4 #6
• 67pts TLE on #4 #5 #6
• AC
• 89pts WA on #4

问：怎样调整可以稳定获得89pts或AC