P14191 [ICPC 2024 Hangzhou R] Elevator II

有一栋 $10^9$ 层的高楼，只有 $1$ 部电梯。最初，电梯停在第 $f$ 层。 现在有 $n$ 个人在等待电梯。第 $i$ 个人现在在第 $l_i$ 层，想通过电梯前往第 $r_i$ 层（$l_i < r_i$）。由于电梯太小，每次最多只能乘坐 $1$ 个人。 每当电梯上升 $1$ 层需要耗费 $1$ 单位电能。如果电梯下降，则不耗费能量。即，从第 $x$ 层到第 $y$ 层的耗电量为 $\max(y-x, 0)$ 单位。 请你安排这 $n$ 个人乘坐电梯的顺序，使得所有人顺利到达目的地且总电能消耗最小。 更正式地，令 $a_1, a_2, \cdots, a_n$ 是 $1\sim n$ 的一个排列，表示第 $i$ 个乘坐电梯的是 $a_i$。总耗电量为 $$\sum\limits_{i = 1}^n (\max(l_{a_i} - r_{a_{(i - 1)}}, 0) + r_{a_i} - l_{a_i})$$ 其中 $a_0 = 0$，$r_0 = f$（即$0$号人的终点为初始电梯位置）。 请你给出最优的搭载顺序，并输出最小的总耗电量。 需要注意，长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ 是 $n$ 的一个排列，当且仅当 $1$ 到 $n$ 的每个整数恰好出现一次。

输入包含多组测试数据。第一行一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。对于每组测试数据： 第一行包含两个整数 $n$ 和 $f$（$1 \le n \le 10^5$，$1 \le f \le 10^9$），分别表示人数和初始电梯所在楼层。 接下来的 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le 10^9$），表示第 $i$ 个人在 $l_i$ 层，希望到达 $r_i$ 层。 保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。

对于每组测试数据，首先输出一行一个整数，表示最小总耗电量。接下来输出一行 $n$ 个空格分隔的整数 $a_1, a_2, \cdots, a_n$，表示乘梯顺序的最优排列。若有多个最优答案，则可输出其中任意一个。

由 ChatGPT 5 翻译