leetcode 1515. 服務中心的最佳位置 随機算法 —— 爬山算法

這題我剛開始用模拟退火，調了半天參數，要麼高精度就T，要麼低精度會wa。

然後看題解都是用爬山算法，就學了一波然後敲了下：

爬山算法的步驟很簡單，就是調步長，然後類似二分向周圍拓展，快速跳過非優值，在最優值附近停止變化步長。

這題模拟退火做不出來的原因應該是精度要求過高，也可能我是菜雞沒調出來參數 QAQ。

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const double PI= acos(-1.0);
const int M = 1e5+7;
int x[55],y[55];
int n,times;
double cal(double a,double b)
{
	double ans=0;
	for(int i=1;i<=n;i++)ans+=sqrt((x[i]-a)*(x[i]-a)+(y[i]-b)*(y[i]-b));
	return ans;
}
double d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
double getMinDistSum(vector<vector<int>>& v)
{
//	n = v.size();
	double step = 10000,eps = 1e-6,best,x0=0,y0=0,x1,y1;
	for(int i=0;i<n;i++)x[i+1]=v[i][0],y[i+1]=v[i][1],x0 += x[i+1],y0 += y[i+1];
	x0/=n,y0/=n;
	x0 = x[1], y0 = y[1];
	best = cal(x0,y0);
	while(step > eps)
	{
		bool f=false;
	//	printf("%lf =  %lf %lf  %lf\n",step,x0,y0,best);
		for(int i=0;i<4;i++)
		{
			x1 = x0 + step * d[i][0];
			y1 = y0 + step * d[i][1];
			double res = cal(x1,y1);
		//	printf("=====    %lf %lf  %lf  \n",x1,y1,res);
			if(res < best)
			{
				f=true;
				x0 = x1,y0 = y1;
				best = res;
			} 
		}
		if(!f)step*=0.7;
	}
	return best;
}
int main()
{ 
	vector<vector<int>>v(55,vector<int>(2));
	int x,y;
	scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d%d",&x,&y),v[i][0]=x,v[i][1]=y;
	printf("%.5lf\n",getMinDistSum(v)); 
	return 0;
}
/*
7
0 1
3 2
4 5
7 6
8 9
11 1
2 12

3 
0 0
1 1
2 0

32.94036
*/