BZOJ-3695. 滑行

Posted by miskcoo on December 5, 2014

这是 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}\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#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;
}