CF1765J Hero to Zero

本题没有英雄。我想我们应该把它命名为“归零”。 给定两个数组 $a$ 和 $b$，每个数组包含 $n$ 个非负整数。 令 $c$ 为一个 $n \times n$ 的矩阵，其中 $c_{i,j} = |a_i - b_j|$，对于每个 $i \in [1, n]$ 和每个 $j \in [1, n]$。 你的目标是将矩阵 $c$ 变为零矩阵，即每个元素都恰好为 $0$。为此，你可以任意次、以任意顺序执行以下操作： - 选择一个整数 $i$，然后将第 $i$ 行的所有元素 $c_{i,j}$（$j \in [1, n]$）都减 $1$。每执行一次该操作，需支付 $1$ 个硬币； - 选择一个整数 $j$，然后将第 $j$ 列的所有元素 $c_{i,j}$（$i \in [1, n]$）都减 $1$。每执行一次该操作，需支付 $1$ 个硬币； - 选择两个整数 $i$ 和 $j$，然后将 $c_{i,j}$ 减 $1$。每执行一次该操作，需支付 $1$ 个硬币； - 选择一个整数 $i$，然后将第 $i$ 行的所有元素 $c_{i,j}$（$j \in [1, n]$）都加 $1$。每执行一次该操作，可获得 $1$ 个硬币； - 选择一个整数 $j$，然后将第 $j$ 列的所有元素 $c_{i,j}$（$i \in [1, n]$）都加 $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$ 变为零矩阵所需的最小硬币数。

在第一个样例中，矩阵如下： $$ \begin{matrix} 1&1&1\\ 0&0&0\\ 1&1&1\\ \end{matrix} $$ 你可以通过如下方式用 $2$ 个硬币将其变为零矩阵： - 对第一行减 $1$，支付 $1$ 个硬币； - 对第三行减 $1$，支付 $1$ 个硬币。 在第二个样例中，矩阵如下： $$ \begin{matrix} 2&2&1\\ 0&0&1\\ 2&2&1\\ \end{matrix} $$ 你可以通过如下方式用 $5$ 个硬币将其变为零矩阵： - 对第一行减 $1$，支付 $1$ 个硬币； - 对第三行减 $1$，支付 $1$ 个硬币； - 对第三行再减 $1$，支付 $1$ 个硬币； - 对 $a_{2,3}$ 减 $1$，支付 $1$ 个硬币； - 对第三列加 $1$，获得 $1$ 个硬币； - 对第一行减 $1$，支付 $1$ 个硬币； - 对 $a_{2,3}$ 再减 $1$，支付 $1$ 个硬币。 由 ChatGPT 4.1 翻译