AT_abc371_f [ABC371F] Takahashi in Narrow Road

题目描述

有一条东西向延伸的道路，道路上有 $N$ 个高桥君。道路从被称为原点的位置向东西方向无限延伸。

第 $i$ 个高桥君（$1\leq i\leq N$）最初位于距离原点向东 $X_i$ 米的位置。

高桥君们可以在道路上向东西方向移动。具体来说，可以任意多次进行如下操作：

• 选择一名高桥君。如果他要移动到的位置上没有其他高桥君，则可以将他向东或向西移动 $1$ 米。

高桥君们共有 $Q$ 个任务，第 $i$ 个（$1\leq i\leq Q$）任务如下：

• 第 $T_i$ 个高桥君需要到达坐标 $G_i$。

请你求出，为了按顺序完成这 $Q$ 个任务，所需的最小移动次数。

输入格式

输入按以下格式从标准输入读入。

$N$ $X_1$ $X_2$ $\ldots$ $X_N$ $Q$ $T_1$ $G_1$ $T_2$ $G_2$
$\vdots$
$T_Q$ $G_Q$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

5
10 20 30 40 50
4
3 45
4 20
1 35
2 60

输出 #1

239

输入输出样例 #2

输入 #2

8
0 1 2 3 4 5 6 100000000
6
1 100000000
8 0
1 100000000
8 4
1 100000000
5 21006578

输出 #2

4294967297

输入输出样例 #3

输入 #3

12
1558 3536 3755 3881 4042 4657 5062 7558 7721 8330 8542 9845
8
9 1694
7 3296
12 5299
5 5195
5 5871
1 2491
8 1149
8 2996

输出 #3

89644

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $0\leq X_1 < X_2 < \dotsb < X_N \leq 10^8$
• $1\leq Q\leq 2\times 10^5$
• $1\leq T_i\leq N\ (1\leq i\leq Q)$
• $0\leq G_i\leq 10^8\ (1\leq i\leq Q)$
• 输入均为整数

样例解释 1

高桥君们的最优行动如下（每个高桥君的坐标未必完全准确）。

每个任务中，高桥君们的移动如下：

• 第 $4$ 个高桥君向东移动 $6$ 次，第 $3$ 个高桥君向东移动 $15$ 次。
• 第 $2$ 个高桥君向西移动 $2$ 次，第 $3$ 个高桥君向西移动 $26$ 次，第 $4$ 个高桥君向西移动 $26$ 次。
• 第 $4$ 个高桥君向东移动 $18$ 次，第 $3$ 个高桥君向东移动 $18$ 次，第 $2$ 个高桥君向东移动 $18$ 次，第 $1$ 个高桥君向东移动 $25$ 次。
• 第 $5$ 个高桥君向东移动 $13$ 次，第 $4$ 个高桥君向东移动 $24$ 次，第 $3$ 个高桥君向东移动 $24$ 次，第 $2$ 个高桥君向东移动 $24$ 次。

高桥君们的总移动次数为 $21+54+79+85=239$ 次。无法在 $238$ 次或更少的移动内完成所有任务，因此请输出 239。

样例解释 2

请注意，过程中有些高桥君可能需要移动到原点以西，或者移动到距离原点 $10^8+1$ 米以东的位置。
另外，答案可能超过 $2^{32}$。

由 ChatGPT 4.1 翻译