题解：P13637 [NWRRC 2021] Journey in Fog

下文中“答案”均为题目所求期望值乘

n

，即

n

种可能性的时间

t

之和。

首先分析 Julia 的最优策略是什么。

设一种策略中，Jane 如果以

v_1,v_2,\dots,v_n

的速度前进，那么 Julia 与她相遇的时间为

t_1,t_2,\dots,t_n

，不难发现

t_1\geq t_2\geq\dots\geq t_n

。则此时答案为

\displaystyle\sum_{i=1}^n(t_i+\frac{L-v_it_i}{V})=\frac{nL}{V}+\frac{1}{V}\displaystyle\sum_{i=1}^n{t_i(V-v_i)}

。

设

p

为使得

|v_p-V|

最小的下标（这意味着

v_p

是

v

中不小于

V

的最小值或者不大于

V

的最大值，这样定义是因为这两个值可能有一个不存在）。如果固定

t_p

，

t_p

时刻 Julia 和 Jane 都固定在

L-t_pv_p

的位置，则：

对于 $i<p$ ， $V-v_i\geq 0$ ，所以希望 $t_i$ 尽可能小，这说明 Julia 在 $t_p$ 时刻如果还没遇到 Jane，就会一直朝 Jane 以最大速度 $V$ 前进；
对于 $i>p$ ， $V-v_i\leq 0$ ，所以希望 $t_i$ 尽可能大。由于速度限制有 $(L-v_pt_p)-(L-v_it_i)\leq V(t_p-t_i)$ ，解得 $t_i\leq\frac{v_p+V}{v_i+V}t_p$ 。当 $t_i$ 取到最大值时，前一条不等式也取等。考虑从 $t_p$ 开始时间倒流回 $0$ ，Julia 从 $L-t_pv_p$ “倒退”回 $0$ 的过程，那么不等式取等就说明在 Julia 是以最大速度 $V$ 从 $L-t_pv_p$ 退回 $L-t_iv_i$ ，所以可以看成 Julia 以最大速度 $V$ 倒退回 $0$ ，并等到时刻 $0$ 。对应到正常的时间上，就是 Julia 先在 $0$ 处等到时刻 $t_p-\frac{L-t_pv_p}{V}$ ，然后以速度 $V$ 向 Jane 前进。

至此说明了 Julia 的最优策略可以表示为：取一个非负实数

x

，先在

0

处等到时刻

x

，如果还没遇到 Jane，就以全速

V

向

L

跑，直到遇到 Jane 后全速折返。由于 Julia 只会以速度

V

移动，第二、三部分的用时相等，那么可以将答案表示为关于

x

的函数：

F(x)=\sum_{i=1}^n\min\{\frac{L}{v_i},x+2\times\frac{\max\{0,L-v_ix\}}{V+v_i}\}

设

I

为满足

\frac{L}{v_I}>x

的最大下标（不存在则为

0

），可将上式重写为：

F(x)=\sum_{i=1}^I(x+2\times\frac{L-v_ix}{V+v_i})+\sum_{i=I+1}^n\frac{L}{v_i}=(\sum_{i=1}^I\frac{V-v_i}{V+v_i})x+\sum_{i=1}^I\frac{2L}{V+v_i}+\sum_{i=I+1}^n\frac{L}{v_i}

所以

F

是一个分段函数，且每一段都是一次函数，而且最后一段斜率为

0

。故最小值只会在所有拐点处取到，即只需要考虑

0

和所有

\frac{L}{v_i}

，不难做到

O(n)

。

文章操作