双指针（简单版） - 問題

Alice 和 Bob 正在一条很长的道路上访问城市，这条道路从点 $-10^9$ 一直延伸到 $10^9$。Alice 从点 $A$ 出发，Bob 从点 $B$ 出发。

有 $n$ 个城市需要访问，第 $i$ 个城市位于点 $t_i$。每个城市都必须至少被 Alice 或 Bob 访问一次，但它们可以按任意顺序访问。

求 Alice 和 Bob 行驶的总距离最小是多少。

每组测试包含多组测试用例。第一行包含一个整数 $T$（$1 \le T \le 100$），表示测试用例组数。每组测试用例的格式如下：

第一行包含三个用空格分隔的整数 $n$、$A$ 和 $B$（$1 \le n \le 2 \cdot 10^5$，$-10^9 \le A, B \le 10^9$），分别表示城市数量、Alice 的位置和 Bob 的位置。

第二行包含 $n$ 个用空格分隔的整数 $t_1, t_2, \ldots, t_n$（$-10^9 \le t_i \le 10^9$），表示各个城市的位置。

保证所有测试用例中的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每组测试用例，输出一行答案。

输出 Alice 和 Bob 为访问所有城市所必须行驶的最小总距离。

子任务 1（$16$ 分）：$n \le 20$，$-10^6 \le A, B, t_i \le 10^6$

子任务 2（$36$ 分）：$n \le 5000$，$-10^6 \le A, B, t_i \le 10^6$

子任务 3（$21$ 分）：$n \le 5000$

子任务 4（$27$ 分）：无额外限制

4
7 -6 10
-15 -1 12 8 11 -6 0
2 -1000000000 -1000000000
1000000000 -1000000000
1 4 6
1
4 727 137
39 852 201 696

在第一组测试用例中：有 $7$ 个城市。Alice 从坐标 $-6$ 出发，Bob 从点 $10$ 出发。

一种可能的最优访问方式如下（$i \xrightarrow{x} j$ 表示从 $i$ 前往 $j$，行驶距离为 $x$）：

Alice 访问城市（按访问顺序给出）：$A \xrightarrow{0} \text{城市 }6 \xrightarrow{9} \text{城市 }1$。
Bob 访问城市（按访问顺序给出）：$B \xrightarrow{1} \text{城市 }5 \xrightarrow{1} \text{城市 }3 \xrightarrow{4} \text{城市 }4 \xrightarrow{8} \text{城市 }7 \xrightarrow{1} \text{城市 }2$。

Alice 总共行驶了 $0 + 9 = 9$ 的距离，Bob 总共行驶了 $1 + 1 + 4 + 8 + 1 = 15$ 的距离。两人总行驶距离为 $9 + 15 = 24$。可以证明，不存在总行驶距离小于 $24$ 的方案，因此答案是 $24$。

在第二组测试用例中，Alice 和 Bob 一开始都已经在城市 $2$ 处。Bob 可以先访问城市 $2$，再访问城市 $1$，总共行驶 $2,000,000,000$ 的距离。注意 Alice 可以选择什么都不做。

在第三组测试用例中，Alice 可以访问唯一的城市，从点 $4$ 行驶到点 $1$，距离为 $3$。Bob 什么都不做。

QOJ.ac