题解 AT3955 【[AGC023D] Go Home】

小粉兔 · 2020-02-25 23:35:14 · 题解

如果 X_1 < S < X_N，考虑第 1 栋楼和第 N 栋楼。

如果 P_1 \ge P_N，即第 1 栋楼中的人数大于等于第 N 栋楼中的人数，则班车一定会先去第 1 栋楼。证明：

• 如果 N = 2，显然成立。
• 如果 N \ge 3 且 X_{N - 1} < S，显然除了第 N 栋楼的员工，都希望前往负方向，所以一定会前往负方向。
• 如果 N \ge 3 且 S < X_{N - 1}，如果在到达第 1 栋楼之前没有到达第 N - 1 栋楼，则结论成立，否则转化为前两种情况。

所以说不管怎么样都会先前往第 1 栋楼，然后就可以一路向右径直跑到第 N 栋楼。

这就意味着，第 N 栋楼中内的员工的回家时间，一定等于第 1 栋楼的回家时间，加上 X_N - X_1。

也就是说，第 N 栋楼中的员工，其实是和第 1 栋楼中的员工站在同一条线上的。第 1 栋楼的员工想投什么票，他们也一定会跟着投。所以说这第 N 栋楼的员工其实和第 1 栋楼的员工没什么区别，暂时（在第 1 栋楼的员工回家之前）让他们搬家到第 1 栋楼也对运行路径没有影响。

所以说，如果让 P_1 \gets P_1 + P_N，然后删去第 N 栋楼，计算这种情况下的到达第 1 栋楼的时间，加上 X_N - X_1 就是答案。

如果 P_1 < P_N，那么以上结论的方向反过来即可。

这样递归下去，直到不满足 X_1 < S < X_N 为止，那样的话就可以直接计算答案了。

时间复杂度 \mathcal O (N)，评测链接。