A16793 · Elevator Against Humanity

题目描述

如今，所有的设备都是智能的：智能手机、智能音箱、智能灯泡，甚至还有智能电梯。机器正在崛起。 人类反抗军的总部正坐落于一座摩天大楼中。然而，智能电梯正试图在不暴露自己的情况下拖慢人们的行动速度。 大楼中有 $n$ 个人分别在不同楼层等候电梯，每个人想去另一个楼层。每个人的目的楼层与其他人的目的楼层以及所有起始楼层都不同。开始时，电梯位于一楼。每单位时间电梯能够移动一层楼。每当电梯开门时，它可以选择下一个要去的楼层并直接前往。电梯可以前往尚未上电梯乘客的起始楼层接他们，或者前往已经在电梯里的乘客的目的楼层送他们下电梯。请注意，电梯不会在中途楼层停靠，即使里面有乘客也是如此。乘客的上电梯和下电梯用时可以忽略。电梯空间足够大，能一次容纳所有人。 电梯的目标是最大化运送所有乘客到达他们的目标楼层所需的总时间。请计算从一楼出发至最后一名乘客下电梯所需的最大总时间。电梯无需返回一楼。

每组测试数据包含多个测试用例。第一行包含测试用例个数 $t$（$1 \le t \le 10\,000$）。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数 $n$，表示等待电梯的人数（$1 \le n \le 10^5$）。 接下来的 $n$ 行中，每行包含两个整数 $s_i$ 和 $f_i$（$2 \le s_i, f_i \le 10^9$），分别表示第 $i$ 个人的起始楼层和目标楼层。输入中的所有 $2n$ 个楼层均两两不同。 保证所有测试用例中 $n$ 的总和不超过 $10^5$。

对于每个测试用例，输出运送所有人的最大所需时间。

输入 #1

输出 #1

6
21
21