乘客需要多运动题解¶
解法比较¶
出题人解法枚举可行区间端点，以及乘客位置与相邻车门中点对齐的位置。在相邻候选之间，每位乘客的最近车门不变，距离为绝对值函数，因此总距离为凸函数，最大值及最左侧最优位置可在候选点取得。对每个候选，把乘客和车门按序用双指针配对，计算到最近车门的总距离。下文的凸性证明沿用此思路。
所有候选坐标均为整数或半整数。Codex（GPT-6）的实现把坐标乘二，以整数精确比较总距离和最左位置，避免浮点容差影响并列判断。设乘客、车门数为 \(M,N\) ，候选计算时间为 \(O(MN(M+N))\) ，空间为 \(O(M+N)\) .
候选位置¶
固定一位乘客。随着 \(S\) 变化，最近车门只可能在两扇相邻门的距离相等处切换，即
在这些切换点之间，乘客到最近门的距离是某个绝对值函数。它在车门恰好对齐乘客的位置出现向上的尖角（局部最小值），在两门等距处可能出现向下的尖角（局部最大值）。所有乘客距离之和在其余区间内为线性函数。因此最大值及最左侧的最大值位置必在区间端点 \(0,L-D_N\) 或某个上述切换点取得。
把所有坐标乘以 \(2\) ，候选位置、最近门距离和总距离均变成整数。可完全使用 64 位整数比较和打破平局。
程序中的 PassengerPositions 和 DoorOffsets 分别保存乘客位置 \(P_i\) 和车门偏移量 \(D_j\) ，数组仍保留输入的原始尺度。计算距离时再乘以 \(2\) ；TwiceStart 保存首扇门停靠坐标的两倍 \(2S\) .
计算一个候选位置的总距离¶
乘客位置已经排序。按顺序扫描乘客，并维护其最近门的编号。乘客位置增大时最近门编号不会减小，因此对一个候选位置的计算只需 \(O(M+N)\) 时间。若两门等距，任选其一。
枚举至多 \(M(N-1)+2\) 个候选位置，计算总距离。先比较总距离，距离相同时选较小的 \(S\) .
正确性¶
只保留合法区间内的候选点，再按位置划分区间。在相邻候选点之间，每位乘客使用的最近门不变，其距离是一个绝对值函数。因此，总距离是凸函数：区间内任意一点的值不超过两端点值的较大者。若内部某点取得全局最大值，则该段至少一个端点也取得最大值；若左端点更小，由凸性可知内部点的值严格小于右端点，矛盾。所以最左侧的最优位置必是候选点。逐一精确计算并按题目规则比较，得到正确答案。
复杂度¶
候选点数量为 \(O(MN)\) ，每次计算花费 \(O(M+N)\) ，总时间 \(O(MN(M+N))\) ，空间 \(O(M+N)\) . 距离之和的两倍至多为 \(2ML\) ，适合 64 位有符号整数。