BZOJ-3695. 滑行

这是 2014 年福建省省队训练的时候首长出的一道题，题目大概是这样的

首长NOI惨跪，于是去念文化课了。现在，他面对一道物理题

现在有一个小滑块可以在地面上滑行，地面上被划分成不同的区域，使得小滑块在不同的区域内部有一个不同的速度上限

小滑块在 $(0，0)$ 点，我们现在要推动小滑块到目标点 $(x, y)$

地面上有 $N$ 层区域，每层区域都是矩形，现在给你一个序列 ${H_i}$ 表示每层区域的高度，覆盖的地面横坐标范围是 $0\sim X$，第 $i$ 个区域的限速是 $v_i$

注： $Y=\sum_{i=1}^nH_i$，其它的地方小滑块不允许进入

现在我们要设计一个路线使得小滑块滑到目标点的用时最小

如果你知道两个物理学的定理（光的最速原理、折射定律），那么这题就可以很快解出来了

光的最速原理是说，光从一点射到另一点，用的路径一定是所有路径中最短的

折射定律是说，光的入射角 $\theta_1$ 和折射角 $\theta_2$ 与光在两块介质中的速度 $v_1,~v_2$ 有如下关系： \[\frac{\sin\theta_1}{v_1}=\frac{\sin\theta_2}{v_2}\]

这样，把滑块类比成光，就可以二分初始角度来计算答案了 但是…… 如果不知道上面那两个东西怎么办呢？ 那我们只能乖乖的来用数学推导了 首先设入射角为 $\theta_1$，折射角为 $\theta_2$，在两块区域的速度分别是 $v_1,~v_2$，两块区域的高度分别是 $h_1,~h_2$ 那么要求的就是最小化 \[ f(\theta_1, \theta_2) = \frac{h_1}{v_1\cos\theta_1}+\frac{h_2}{v_2\cos\theta_2} \] 并且还有一个限制条件 \[ h_1\tan\theta_1 + h_2\tan\theta_2 = d \]

于是问题变成了求有约束条件的优化问题，数学上有一种叫做拉格朗日乘数法的东西，可以用来解决这个问题 也就是设 \[\Phi(\theta_1, \theta_2) = h_1\tan\theta_1 + h_2\tan\theta_2 - d \] \[F(\theta_1, \theta_2) = f(\theta_1, \theta_2) + \lambda \Phi(\theta_1, \theta_2)\]

这样，当 $f(\theta_1, \theta_2)$ 在限制条件 $\Phi(\theta_1, \theta_2)$ 下得到最优值时

\[\begin{eqnarray*} \left\{ \begin{aligned} \frac{\partial F}{\partial \theta_1} = 0\\ \frac{\partial F}{\partial \theta_2} = 0\\ \frac{\partial F}{\partial \lambda} = 0 \end{aligned} \right. \end{eqnarray*}\]

也就是 \(\begin{eqnarray*} \left\{ \begin{aligned} \frac{\sin\theta_1}{v_1}+\lambda ~&= 0\\ \frac{\sin\theta_2}{v_2}+\lambda ~&= 0\\ \Phi(\theta_1, \theta_2) ~&= 0 \end{aligned} \right. \end{eqnarray*}\)

最后得到的也是 \(\frac{\sin\theta_1}{v_1}=\frac{\sin\theta_2}{v_2}\)

#include <cstdio>
#include <cmath>

int n, x;
int velocity[100], height[100];

double solve(double sin)
{
	double dist = 0.0;
	for(int i = 0; i != n; ++i)
	{
		double tan = sin / std::sqrt(1.0 - sin * sin);
		dist += tan * height[i];
		if(i + 1 != n)
			sin = sin / velocity[i] * velocity[i + 1];
		if(sin > 1.0) return x + 1.0;
	}

	return dist;
}

double calc_time(double sin)
{
	double time = 0.0;
	for(int i = 0; i != n; ++i)
	{
		double cos = std::sqrt(1.0 - sin * sin);
		time += height[i] / (cos * velocity[i]);
		if(i + 1 != n)
			sin = sin / velocity[i] * velocity[i + 1];
	}

	return time;
}

int main()
{
	std::scanf("%d %d", &n, &x);
	for(int i = 0; i != n; ++i)
		std::scanf("%d", height + i);
	for(int i = 0; i != n; ++i)
		std::scanf("%d", velocity + i);
	double l = 0.0, r = 1.0;
	for(int i = 0; i != 100; ++i)
	{
		double m = (l + r) * 0.5;
		double dist = solve(m);
		if(dist > x) r = m;
		else l = m;
	}

	std::printf("%.3lf", calc_time(l));
	return 0;
}