A6979. 兄妹
编程题
普及+/提高
知识点
题目描述
小 Y 和小 S 在同一家书店工作，今天他们需要将新进货的书放到书架上。书店的书架平行排成若干排，书架的位置可以看作平面直角坐标系中的整点。第 $r$ 排书架包含横坐标为 $r$，纵坐标 $\ge0$ 的点，出入口为 $(r,0)$。
他们每一秒可以走到坐标系中一个相邻的整点。在同一排书架中可以自由走动，但在不同排书架间移动时，由于会被书架挡住，只能从出入口离开后从书架外侧绕行。
形式化地，他们每秒可以从 $(r,c)$ 走到 $(r,c\pm1)$，或者从 $(r,0)$ 走到 $(r\pm1,0)$，但若 $c\ge1$，则不能从 $(r,c)$ 走到 $(r\pm1,c)$。
现在有 $n$ 本新书，第 $i$ 本要放到 $(r_i,c_i)$。他们要从 $(0,0)$ 处的书库出发，把所有新书放到对应的书架上。他们可以带着任意多本书移动，到达书架 $(r,c)$ 时可以立刻把所有要放到 $(r,c)$ 的书放上书架，往书架上放书的时间可以忽略不计。
现在他们要把书分成两部分，每人负责其中一部分，最后返回出发点 $(0,0)$。他们想要知道，怎样适当分配两人负责的书，可以使得用时较长者的用时最短。
他们每一秒可以走到坐标系中一个相邻的整点。在同一排书架中可以自由走动，但在不同排书架间移动时，由于会被书架挡住，只能从出入口离开后从书架外侧绕行。
形式化地，他们每秒可以从 $(r,c)$ 走到 $(r,c\pm1)$，或者从 $(r,0)$ 走到 $(r\pm1,0)$，但若 $c\ge1$，则不能从 $(r,c)$ 走到 $(r\pm1,c)$。
现在有 $n$ 本新书，第 $i$ 本要放到 $(r_i,c_i)$。他们要从 $(0,0)$ 处的书库出发，把所有新书放到对应的书架上。他们可以带着任意多本书移动，到达书架 $(r,c)$ 时可以立刻把所有要放到 $(r,c)$ 的书放上书架，往书架上放书的时间可以忽略不计。
现在他们要把书分成两部分，每人负责其中一部分，最后返回出发点 $(0,0)$。他们想要知道，怎样适当分配两人负责的书，可以使得用时较长者的用时最短。
输入格式
**本题有多组测试数据。**
输入的第一行包含一个正整数 $T$，表示数据组数。
接下来包含 $T$ 组数据，每组数据的格式如下：
第一行包含一个整数 $n$，表示有 $n$ 本书。
接下来 $n$ 行：
第 $i$ 行包含两个整数 $r_i,c_i$ 表示第 $i$ 本书要放到书架 $(r_i,c_i)$。
输入的第一行包含一个正整数 $T$，表示数据组数。
接下来包含 $T$ 组数据，每组数据的格式如下：
第一行包含一个整数 $n$，表示有 $n$ 本书。
接下来 $n$ 行：
第 $i$ 行包含两个整数 $r_i,c_i$ 表示第 $i$ 本书要放到书架 $(r_i,c_i)$。
输出格式
对于每组数据，输出一行包含一个整数，表示用时较长者的最短可能用时。
输入输出样例
输入 #1
1 3 1 2 2 3 3 1
输出 #1
12
说明/提示
**【样例 1 解释】**
如果小 Y 负责第 $1,3$ 本书，小 S 负责第 $2$ 本书，那么他们可以按如下路径前往对应书架并返回：
+ 小 Y：$(0,0)\to(1,0)\to(1,2)\to(1,0)\to(3,0)\to(3,1)\to(3,0)\to(0,0)$，总用时 $12$ 秒。
+ 小 S：$(0,0)\to(2,0)\to(2,3)\to(2,0)\to(0,0)$，总用时 $10$ 秒。
用时较长者用时 $12$ 秒，可以证明不存在更优的方案。
**【数据范围】**
对于所有数据，保证：$1\le T\le5$，$1\le n\le10^5$，$1\le r_i,c_i\le500$。
| 测试点编号 | $n\le$ | $r_i\le$ | $c_i\le$ |
| :-: | :-: | :-: | :-: |
| $1$ | $10$ | $10$ | $10$ |
| $2$ | $100$ | $100$ | $2$ |
| $3\sim4$ | ^ | ^ | $100$ |
| $5\sim6$ | $10^5$ | ^ | $2$ |
| $7\sim9$ | ^ | ^ | $100$ |
| $10$ | ^ | $500$ | $500$ |
如果小 Y 负责第 $1,3$ 本书，小 S 负责第 $2$ 本书，那么他们可以按如下路径前往对应书架并返回：
+ 小 Y：$(0,0)\to(1,0)\to(1,2)\to(1,0)\to(3,0)\to(3,1)\to(3,0)\to(0,0)$，总用时 $12$ 秒。
+ 小 S：$(0,0)\to(2,0)\to(2,3)\to(2,0)\to(0,0)$，总用时 $10$ 秒。
用时较长者用时 $12$ 秒，可以证明不存在更优的方案。
**【数据范围】**
对于所有数据，保证：$1\le T\le5$，$1\le n\le10^5$，$1\le r_i,c_i\le500$。
| 测试点编号 | $n\le$ | $r_i\le$ | $c_i\le$ |
| :-: | :-: | :-: | :-: |
| $1$ | $10$ | $10$ | $10$ |
| $2$ | $100$ | $100$ | $2$ |
| $3\sim4$ | ^ | ^ | $100$ |
| $5\sim6$ | $10^5$ | ^ | $2$ |
| $7\sim9$ | ^ | ^ | $100$ |
| $10$ | ^ | $500$ | $500$ |