分数: 500 点
问题陈述
有 N 球,称为 Ball 1 通过 N,在数轴上。
球 i 位于坐标处 X_i.
每个球都有一个由整数 ID 表示的颜色 1 和 N (含);球颜色的ID i is C_i.
您现在位于坐标 0。您将以以下速度沿线移动来收集所有球
每秒 1 ,然后返回坐标 0.
在这里,您必须按照 ID 的非降序收集球。
收集球时,您必须位于该球的坐标处,但并不强制要求您在该坐标处收集球。
求从该坐标开始所需的最短时间 0,收集所有球,并返回坐标 0.
约束
- 1 \le N \le 2 \times 10^5
- |X_i| \le 10^9
- X_i \neq X_j (i \neq j)
- X_i \neq 0
- 1 \le C_i \le N
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
X_1 C_1
X_2 C_2
X_3 C_3
\hspace{15pt} \vdots
X_N C_N
输出
打印所需的秒数。
示例输入 1
5 2 2 3 1 1 3 4 2 5 3
示例输出 1
12
最优策略是:
- 花费 3 秒到达坐标 3 并收集球 2;
- 花费 1 第二次到达坐标 2 并收集球 1;
- 花费 2 秒到达坐标 4 并收集球 4;
- 花费 1 第二次到达坐标 5 并收集球 5;
- 花费 4 秒到达坐标 1 并收集球 3;
- 花费 1 第二次返回坐标 0.
在这里,我们按照 ID 的非降序收集球: 1, 2, 2, 3, 3.
示例输入 2
9 5 5 -4 4 4 3 6 3 -5 5 -3 2 2 2 3 3 1 4
示例输出 2
38