← 返回题目列表

Codeforces · 1765/J

J. 英雄归零

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

这个问题没有英雄。我想我们应该将其命名为“To Zero”。

给定两个数组 $$$a$$$ 和 $$$b$$$,每个数组都包含 $$$n$$$ 非负整数。

令 $$$c$$$ 为大小为 $$$n \times n$$$ 的矩阵,使得 $$$c_{i,j} = |a_i - b_j|$$$ 对于 [1, n]$$$ 中的每个 $$$i \in 和 [1, n]$$$ 中的每个 $$$j \。

你的目标是变换矩阵 $$$c$$$ 使其成为零矩阵,i。 e.每个元素恰好为 $$$0$$$ 的矩阵。为此,您可以按任意顺序多次执行以下操作:

- 选择一个整数 $$$i$$$,然后对 [1, n]$$$ 中的每个 $$$j \in 将 $$$c_{i,j}$$$ 减少 $$$1$$$ (即,将第 $$$i$$$ 行中的所有元素减少 $$$1$$$)。为了执行此操作,您需要支付 $$$1$$$ 硬币;
- 选择一个整数 $$$j$$$,然后对 [1, n]$$$ 中的每个 $$$i \in 将 $$$c_{i,j}$$$ 减少 $$$1$$$ (即,将第 $$$j$$$ 列中的所有元素减少 $$$1$$$)。为了执行此操作,您需要支付 $$$1$$$ 硬币;
- 选择两个整数 $$$i$$$ 和 $$$j$$$,然后将 $$$c_{i,j}$$$ 减去 $$$1$$$。为了执行此操作,您需要支付 $$$1$$$ 硬币;
- 选择一个整数 $$$i$$$,然后对 [1, n]$$$ 中的每个 $$$j \in 将 $$$c_{i,j}$$$ 增加 $$$1$$$ (即,将第 $$$i$$$ 行中的所有元素增加 $$$1$$$)。当您执行此操作时,您将收到$$$1$$$硬币;
- 选择一个整数 $$$j$$$,然后对 [1, n]$$$ 中的每个 $$$i \in 将 $$$c_{i,j}$$$ 增加 $$$1$$$ (即,将第 $$$j$$$ 列中的所有元素增加 $$$1$$$)。当您执行此操作时,您将收到 $$$1$$$ 硬币。

你必须计算将矩阵 $$$c$$$ 转换为零矩阵所需的最小硬币数量。请注意,操作后$$$c$$$ 的所有元素应同时等于$$$0$$$。

输入

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

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^8$$$)。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$0 \le b_j \le 10^8$$$)。

输出

打印一个整数 — 将矩阵 $$$c$$$ 转换为零矩阵所需的最小硬币数量。

示例

输入 #1

3
1 2 3
2 2 2

输出 #1

2

输入 #2

3
3 1 3
1 1 2

输出 #2

5

输入 #3

2
1 0
2 1

输出 #3

2

输入#4

2
1 4
2 3

输出#4

4

输入 #5

4
1 3 3 7
6 9 4 2

输出 #5

29

注意

在第一个示例中,矩阵如下所示:

111000111

您可以使用$$$2$$$硬币将其变成零矩阵,如下所示:

- 从第一行减去$$$1$$$,支付$$$1$$$硬币;
- 从第三行减去$$$1$$$,支付$$$1$$$硬币。

在第二个示例中,矩阵如下所示:

221001221

您可以使用 $$$5$$$ 硬币将其变成零矩阵,如下所示:

- 从第一行减去$$$1$$$,支付$$$1$$$硬币;
- 从第三行减去$$$1$$$,支付$$$1$$$硬币;
- 从第三行减去$$$1$$$,支付$$$1$$$硬币;
- 从$$$a_{2,3}$$$中减去$$$1$$$,支付$$$1$$$硬币;
- 将$$$1$$$添加到第三列,收到$$$1$$$硬币;
- 从第一行减去$$$1$$$,支付$$$1$$$硬币;
- 从 $$$a_{2,3}$$$ 中减去 $$$1$$$,支付 $$$1$$$ 硬币。