← 返回题目列表

Codeforces · 1651/C

C. 容错网络

中文机器翻译题面 查看原题

有一间教室,有两排电脑。每排有 $$$n$$$ 台计算机,每台计算机都有自己的等级。第一行计算机的等级为 $$$a_1、a_2、\dots、a_n$$$,第二行计算机的等级为 $$$b_1、b_2、\dots、b_n$$$。

最初,每行中的所有相邻计算机对都通过电线连接(对 $$$(i, i + 1)$$$ 对于所有 $$$1 \le i < n$$$),因此两行形成两个独立的计算机网络。

您的任务是通过连接来自不同行的一对或多对计算机,将它们组合到一个公共网络中。连接第一行的第 $$$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

2
3
1 10 1
20 4 25
4
1 1 1 1
1000000000 1000000000 1000000000 1000000000

输出 #1

31
1999999998

注意

在第一个测试用例中,最好连接四对计算机:

1. 第一行的计算机 $$$1$$$ 和第二行的计算机 $$$2$$$:成本 $$$|1 - 4| = 3$$$;
2. 第一行的计算机 $$$3$$$ 和第二行的计算机 $$$2$$$:成本 $$$|1 - 4| = 3$$$;
3. 第一行的计算机 $$$2$$$ 和第二行的计算机 $$$1$$$:成本 $$$|10 - 20| = 10$$$;
4. 第一行的计算机 $$$2$$$ 和第二行的计算机 $$$3$$$:成本 $$$|10 - 25| = 15$$$;

在第二个测试用例中,最好将第一行的 $$$1$$$ 与第二行的 $$$1$$$ 连接,将第一行的 $$$4$$$ 与第二行的 $$$4$$$ 连接。