题解

思路

竖直移动免费且只能发生在两侧边界，因此只需考虑每个有门的行中怎样支付水平代价。

做法

若完全不用右侧电梯，第 $i$ 个有门行只要从左端走到该行最右的门再返回，总代价为这些 $2(B_{\max}-1)$ 之和。若使用右侧电梯，把该行门的列坐标排序，并补上哨兵 $1,W$；不横穿该行时，可以分别从左右两端往返，最佳代价等于 $2(W-1)$ 减去相邻坐标最大间隙的两倍。横穿一行的代价恒为 $W-1$，而从左侧出发并最终回到左侧要求横穿行数为正偶数。

于是先计算“不用右侧电梯”的答案；再把每行不横穿时的代价从大到小排序，从零个横穿行的代价和出发，每次把接下来的两行改为横穿，并更新答案。选择相同数量的横穿行时显然应替换原代价最大的若干行，因此该贪心覆盖了所有可行偶数。

复杂度

对所有门按行、列排序即可求出每行的最右门与最大间隙，随后再排序各行代价，总时间复杂度为 $O(N\log N)$，空间复杂度为 $O(N)$。