题解：P13637 [NWRRC 2021] Journey in Fog
complexor
·
·
题解
下文中“答案”均为题目所求期望值乘 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)。