← 返回题目列表

Codeforces · 1513/F

F. 交换问题

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

给你 2 个数组 $$$a$$$ 和 $$$b$$$,大小都是 $$$n$$$。 $$$b$$$ 中的两个元素最多可以交换一次(或者保持原样),并且需要最小化 $$$$$$\sum_{i}|a_{i}-b_{i}|.$$$$$$ 的值

找到该总和的最小可能值。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le {10^9}$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le {10^9}$$$)。

输出

输出$$$\sum_{i}|a_{i}-b_{i}|$$$的最小值。

示例

输入 #1

5
5 4 3 2 1
1 2 3 4 5

输出 #1

4

输入 #2

2
1 3
4 2

输出 #2

2

注意

在第一个示例中,我们可以交换数组 $$$b$$$ 中的第一个和第五个元素,使其变为 $$$[ 5, 2, 3, 4, 1 ]$$$。

因此,该总和的最小可能值为 $$$|5-5| + |4-2| + |3-3| + |2-4| + |1-1| = 4$$$。

在第二个示例中,我们可以交换第一个和第二个元素。所以,我们的答案是$$$2$$$。