题解：AT_arc219_c [ARC219C] Traveling Door-to-Door Salesman (Elevator)

沉石鱼惊旋 · 2026-05-13 13:00:28 · 题解

分两种情况讨论：一直只在最左侧的 1 列移动，还是要涉及到最右侧的 m 列。

先把每一行的关键点排序。

一直在最左侧的 1 列移动是好做的，每一行的关键点，最右侧的那个记作 r，则 \sum 2(r-1) 即为这种情况的答案，就是每一行过去摸一下就回来。

然后一种是两侧都能用。我们先抛开走到 m 列的代价，每一行的代价是，\min\{2(p_i-1)+2(m-p_{i+1})\}，就是走到 1 列摸一下走回去，加上走到 m 列摸一下走回去。钦定 p_0=1,p_{k+1}=m。

现在的基础代价是 2(m-1)+\sum \min\{2(p_i-1)+2(m-p_{i+1})\}，因为还得走到 m 列再走回来。

但是走到 m 列再走回来，这个无形之中就可以再消掉两行的代价！我们找到 \min\{2(p_i-1)+2(m-p_{i+1})\} 很大的一行，可以选择在这一行从 1 走到 m，这样就抵掉了这一行的。同理，最后走回来的时候也可以抵掉一行的代价。

总之我们每次可以这样操作：基础代价为 \sum \min\{2(p_i-1)+2(m-p_{i+1})\}，加上 2(m-1)，然后选不超过两行，把它们的代价扣掉。

用一个大根堆维护每一行的 \min\{2(p_i-1)+2(m-p_{i+1})\} 即可。为了方便实现还可以提前往里面加一个 0 防止最后只选一行的情况没写明白。

https://atcoder.jp/contests/arc219/submissions/75702894