这个问题没有英雄。我想我们应该将其命名为“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$$$ 硬币。