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;
}