CF1651C Fault-tolerant Network

有一个教室里有两排电脑。每排有 $n$ 台电脑，每台电脑都有自己的评分。第一排电脑的评分为 $a_1, a_2, \dots, a_n$，第二排电脑的评分为 $b_1, b_2, \dots, b_n$。 最初，每一排中所有相邻的电脑对都通过电线连接（即所有 $1 \le i < n$ 的 $(i, i+1)$ 对），因此两排各自形成了两个独立的计算机网络。 你的任务是通过连接一对或多对来自不同排的电脑，将它们合并成一个共同的网络。连接第一排的第 $i$ 台电脑和第二排的第 $j$ 台电脑的费用为 $|a_i - b_j|$。 你可以让一台电脑连接多台其他电脑，但你需要至少提供基本的容错能力：你需要以这样的方式连接电脑，使得即使有一台电脑损坏（无论是哪一台），网络也不会被分成两部分或更多部分。 请问，构建一个容错网络的最小总费用是多少？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。接下来有 $t$ 组测试数据。 每组测试数据的第一行包含一个整数 $n$（$3 \le n \le 2 \cdot 10^5$），表示每排电脑的数量。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示第一排电脑的评分。 第三行包含 $n$ 个整数 $b_1, b_2, \dots, b_n$（$1 \le b_i \le 10^9$），表示第二排电脑的评分。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，输出一个整数，表示构建容错网络的最小总费用。

在第一个测试用例中，最优的做法是连接四对电脑： 1. 第一排的第 $1$ 台电脑与第二排的第 $2$ 台电脑相连：费用为 $|1 - 4| = 3$； 2. 第一排的第 $3$ 台电脑与第二排的第 $2$ 台电脑相连：费用为 $|1 - 4| = 3$； 3. 第一排的第 $2$ 台电脑与第二排的第 $1$ 台电脑相连：费用为 $|10 - 20| = 10$； 4. 第一排的第 $2$ 台电脑与第二排的第 $3$ 台电脑相连：费用为 $|10 - 25| = 15$； 总费用为 $3 + 3 + 10 + 15 = 31$。在第二个测试用例中，最优做法是将第一排的第 $1$ 台电脑与第二排的第 $1$ 台电脑相连，将第一排的第 $4$ 台电脑与第二排的第 $4$ 台电脑相连。 由 ChatGPT 4.1 翻译