拉格朗日解题报告

(思路来源：BZOJ 滑行)

题意

在无穷大的水平面上有一个平面直角坐标系。N-1 条垂直于 x 轴的直线将空间分为了 N 个区域。

你被要求把 $(0,0)$处的箱子匀速推到 $(x,y)$。

箱子受水平面的摩擦力与正压力正相关，所以在每个区域的摩擦力可以表示为 $f_i$。$[0,x]$间的坐标轴在每一块区域内的长度为 $d_i$。

那么，你把箱子推到目的地做的最小功是多少呢？(不考虑改变速度时的做功)

拉格朗日乘子法

一个显然的结论是：在每一块区域内的运动成直线，区域间改变方向。这样一定会比走曲线优。

还有一个显然的结论是：箱子的 $y$坐标一定单调。

因此，我们可以设箱子 $y$坐标在每格内的变化量为 $y_i$，那么我们可以列出最优化函数和约束方程：

$$
\begin{align}
F(y_i) &=\sum f_i\sqrt{d_i^2+y_i^2} \
s.t.\ G(y_i) &= \sum f_i – Y = 0
\end{align}
$$

利用拉格朗日乘子法，我们可以知道 $F$在何时取到最小值。

该问题的拉格朗日函数为：
$$
L(y_i,\lambda) = F(y_i)-\lambda G(y_i)
$$
对于 $y_i$和 $\lambda$求偏导，当每个偏导同时为 $0$时，函数取到最小值。

$$
\begin{align}
\frac{\partial L}{\partial y_i} &= \frac{f_i y_i}{\sqrt{d_i^2+y_i^2}}-\lambda = 0 \
\frac{\partial L}{\partial \lambda} &= Y-\sum{y_i} = 0
\end{align}
$$

观察这两个方程，我们发现，对于任意一个 $\lambda$，第一个方程在正数域内都有唯一解。因此，给定一个 $\lambda$，我们可以确定所有的 $y$，但是我们又发现，这样得到的 $y$不满足第二个偏导为 $0$。

因此，我们需要找到一个合适的 $\lambda$，使得通过第一个方程解得的 $y$满足第二个方程。

注意到第一个方程的 $y$在正数域内随 $\lambda$单调下降，因此，我们可以通过二分 $\lambda$找合适的解。

最后求得的 $y_i$带入 $F(y_i)$即可求得答案。

光学原理

该方法有关光的折射原理：

设：入射光线与法线的夹角 $\theta_1$，出射光线与法线的夹角 $\theta_2$，入射面介质内光速 $v_1$，出射面介质内光速 $v_2$。

$$
\frac{\sin(\theta_1)}{v_1} = \frac{\sin(\theta_2)}{v_2}
$$

以及费马原理：
过两个定点的光走且仅走 光程的一阶变分为零的路径。即光一般走的是邻域内的最快的路线。

有了这两个原理，我们就可以把推箱子和光的传播联系在一起。

我们知道光在空间中传播的耗时为：
$$
\frac{L}{c}
$$
而推箱子的做功为：
$$
Lf
$$
因此，我们令每一段区间的 “光速” 为 $\frac{1}{f}$，则，箱子的最优推行路线就是空间中的光路。确定了箱子初始的运行角度，我们就可以得到箱子最终到达的位置。由于这个位置关于初始角度单调，我们只需要二分这个角度，判断到达位置在 $(x,y)$的上方还是下方即可。

但是要注意一点，光在两个介质的光速差异很大，且入射角很大的时候，会发生全反射，推箱子同理。在二分的时候要特殊处理这种情况。