玄学做法(指模拟退火)70分
查看原帖
玄学做法(指模拟退火)70分
398312
国王的新账号楼主2021/7/25 11:35
#include<bits/stdc++.h>
using namespace std;
int n;
double ansx,ansh;
double x[110],y[110];
double sh(double now)
{
	double ans=0;
	for(int i=2;i<=n;i++){
		double slp=(y[i]-y[i-1])/(x[i]-x[i-1]);
		ans=max(ans,y[i-1]+(now-x[i-1])*slp);
	}
	return ans;
}
//计算最低高度 
double lh(double now)
{
	int l=1,r=n;
	while(l+1<r){
		int mid=l+r>>1;
		if(now>x[mid])	l=mid;
		else	r=mid;
	}
	double slp=(y[r]-y[l])/(x[r]-x[l]);
	return y[l]+(now-x[l])*slp;
}
//二分计算最低地面高度 
void sa()
{
	double t=x[n]-x[1],del=0.99;
	while(t>1e-15){
		double ex=(ansx+((rand()*2.0-RAND_MAX)/RAND_MAX)*t);
		double eh=sh(ex)-lh(ex);
		double de=eh-ansh;
		if(de<0){
			ansx=ex;
			ansh=eh;
		}else if(rand()<exp(-de/t)*RAND_MAX){
			ansx=ex;
		}
		t*=del;
	}
}
//退火 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%lf",&x[i]);
		ansx+=x[i];
	}
	for(int i=1;i<=n;i++)	scanf("%lf",&y[i]);
	ansx/=n;
	ansh=sh(ansx)-lh(ansx);
	for(int i=1;i<=10;i++)	sa();
	printf("%.3f",ansh);
	return 0;
}

已经调了一天。。。救救孩子吧

2021/7/25 11:35
加载中...