笔记

解法一：

  • 结论：人数刚刚过半的那个点就是目标点
  • 证明：

alt

  • 实现：统计每个点的人数，然后对其求前缀和

解法二：

先求出所有人到一号点的总路程，然后计算目标点从1变成2的时候的总路程的变化量来计算目标点为2时的总路程。

dist(x+1) = dist(x) + (Px+1 - Px) * (x及其之前的人数 - x+1及其之后的人数)