BZOJ 3695 滑行 迭代+二分

题目大意：给定一个n层的区域，从左下角走到右上角，每个区域的高度和速度都不同，问怎么走最快

由于我并不知道光路最速原理所以我写了迭代+二分23333

首先易知每一层的路线都一定是一条直线

我们考虑只有两层的情况 由于左下角和右上角固定 因此我们可以三分确定中间的转折点的位置

或者可以写出时间关于转折点坐标的函数关系 求导之后二分 这个更快一些

那么现在是多层 我们这样搞：

每次迭代，枚举1~n-1的每个转折点，对于第i个转折点确定第i-1个点和第i+1个点的位置，二分确定第i个转折点

这样迭代4000次就能出结果了= = 果断BZ倒数第一

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 110
#define EPS 1e-3
using namespace std;
int n;
double X[M],Y[M],v[M];
double sqr(double x)
{
	return x*x;
}
double Bisection(int i)
{
	double l=X[i-1],r=X[i+1];
	while(r-l>EPS)
	{
		double mid=(l+r)/2;
		double temp=(mid-X[i-1])/sqrt(sqr(mid-X[i-1])+sqr(Y[i]))/v[i]+(mid-X[i+1])/sqrt(sqr(mid-X[i+1])+sqr(Y[i+1]))/v[i+1];
		if(temp>0)
			r=mid;
		else
			l=mid;
	}
	return (l+r)/2;
}
int main()
{
	int i,j;
	cin>>n;cin>>X[n];
	for(i=1;i<=n;i++)
		scanf("%lf",&Y[i]);
	for(i=1;i<=n;i++)
		scanf("%lf",&v[i]);
	for(i=1;i<n;i++)
		X[i]=X[n]/n*i;
	double delta=0;
	for(i=1;i<=4000; ++i)
	{
		delta=0;
		for(j=1;j<n;j++)
		{
			double temp=X[j];
			X[j]=Bisection(j);
			delta+=fabs(temp-X[j]);
		}
		if(delta<EPS)
			break;
	}
	double ans=0;
	for(i=1;i<=n;i++)
		ans+=sqrt(sqr(X[i]-X[i-1])+sqr(Y[i]))/v[i];
	printf("%.3lf\n",ans);
	return 0;
}

原文：http://blog.csdn.net/popoqqq/article/details/44649799