题目是说有一群小贩分布在一条街上。现在他们要分开,即使得任意两个人之间的距离不小于$D$,免得互相抢生意。小贩走路的速度是恒定且相同的。求分开的最短时间。

答案里面的数学解法看上去挺漂亮的。首先观察到小贩们的运动不会交叉。然后对于编号为$i < j$的任意两个小贩(称为一个pair),设他们的当前距离为$d(i,j) = P_j - P_i$,想要达到的距离为$D(i,j) = D \cdot (j

  • i)$。不妨称前面的为现实距离,后面的为理想距离好了。然后找到理想距离与现实距离的差的最大值$X = \max(D(i,j) - d(i,j))$。差距 为$X$的pair可能有一组或多组,称这样的pair为$X$-pair。一个observation是一个小贩不可能既是一个$X$-pair的左端点,又是另一 个$X$-pair的右端点,不然其余两个端点的现实距离与理想距离的差距会更大,矛盾。

这就好了。让每个$X$-pair的左端点向左跑,右端点向右跑,现实距离就增大了,与理想的差距就缩小了,而且这个过程是以2倍速在进行。注意他们是不可能撞在一起 的,否则上面推矛盾的方法照用。也就是说即便从运动方向判断可能撞在一起,实际上在相撞之前所有$X$-pair构成的集合就动态变化了。那么$X$值总是以2倍速减 小。$X = 0$的时候就是条件满足的时候。如果一开始$X > 0$的话,只需要$X/2$时间。如果一开始$X \leq 0$的话就什么都不用做,也就是时间为0。

最后说明求$X$的时候可以线性。因为小贩的顺序不会变,可以顺序求$D(i,i+1) - d(i,i+1)$,边累加边维护最大值。当前累加值如果小于0就丢弃。其实就是连续子序列最大和的贪心。