A. Swap Columns and Find a Path 详细题解

问题重述

有一个 $2$ 行 $n$ 列的矩阵。你可以任意交换整列（交换两列的所有元素）。操作结束后，你需要从 $(1,1)$ 走到 $(2,n)$，每次只能向下或向右，路径恰好包含 $n+1$ 个格子。要求最大化路径上所有格子数值之和。

---

关键观察

任何一条合法路径必然在某列 $k$ 处从第一行换到第二行（即经过 $(1,k)$ 和 $(2,k)$），然后一直向右走到 $(2,n)$。路径的形态为：

• 第一行的第 $1$ 列到第 $k$ 列：$(1,1),(1,2),\dots,(1,k)$
• 第二行的第 $k$ 列到第 $n$ 列：$(2,k),(2,k+1),\dots,(2,n)$

因此，总共有 $n+1$ 个格子，其中 $(1,k)$ 和 $(2,k)$ 都是路径的一部分，但 $(2,k)$ 只被计算一次。

---

列的分类

可以将所有列分为三类：

1. 只经过上格子的列：路径中只取该列的第一行格子。
2. 只经过下格子的列：路径中只取该列的第二行格子。
3. 经过两个格子的列：即换行的那一列，路径中同时取该列的第一行和第二行。

换行列恰好只有一列（记作第 $p$ 列）。其他列可以根据需要分配到第一组或第二组：

• 若想将某列作为第一组，就把它放在 $p$ 列之前；
• 若想作为第二组，就放在 $p$ 列之后。
  由于可以自由交换列，我们实际上可以任意决定哪些列属于第一组，哪些属于第二组，只要换行列固定即可。

---

代价公式

设第 $i$ 列的两个数值为 $a_{1,i}$ 和 $a_{2,i}$。

• 若第 $i$ 列属于第一组（只走上格），贡献为 $a_{1,i}$。
• 若属于第二组（只走下格），贡献为 $a_{2,i}$。
• 若为换行列（第 $p$ 列），贡献为 $a_{1,p}+a_{2,p}$。

因此，选定换行列 $p$ 后，总代价为：

$$\text{cost}(p) = (a_{1,p}+a_{2,p}) + \sum_{i \neq p} \max(a_{1,i}, a_{2,i}) $$

这是因为对于非换行列，我们可以自由选择将它放在第一组或第二组，从而获得该列中较大的那个数（因为我们可以决定该列是走上格还是下格来获得较大的值）。

---

优化计算

设 $S = \sum_{i=1}^n \max(a_{1,i}, a_{2,i})$，即所有列的最大值之和。
则对于换行列 $p$：

$$\text{cost}(p) = S + (a_{1,p}+a_{2,p}) - \max(a_{1,p}, a_{2,p}) $$

因为原来 $S$ 中包含了 $\max(a_{1,p},a_{2,p})$，而换行列实际贡献的是 $a_{1,p}+a_{2,p}$，所以需要减去原来的 $\max$ 再加上 $a_{1,p}+a_{2,p}$。

而 $a_{1,p}+a_{2,p} - \max(a_{1,p},a_{2,p}) = \min(a_{1,p},a_{2,p})$。
因此：

$$\text{cost}(p) = S + \min(a_{1,p}, a_{2,p})$$

所以答案就是：

$$\max_{1 \le p \le n} \big( S + \min(a_{1,p}, a_{2,p}) \big) $$

---

算法步骤

1. 计算 $S = \sum_{i=1}^n \max(a_{1,i}, a_{2,i})$。
2. 对于每个 $i$，计算 $S + \min(a_{1,i}, a_{2,i})$，取最大值。
3. 输出该最大值。

时间复杂度 $O(n)$，空间 $O(1)$。

---

参考代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<ll> a1(n), a2(n);
        for (int i = 0; i < n; ++i) cin >> a1[i];
        for (int i = 0; i < n; ++i) cin >> a2[i];
        ll sum_best = 0;
        vector<ll> best(n), full(n);
        for (int i = 0; i < n; ++i) {
            best[i] = max(a1[i], a2[i]);
            full[i] = a1[i] + a2[i];
            sum_best += best[i];
        }
        ll ans = -1e18;
        for (int i = 0; i < n; ++i) {
            ans = max(ans, sum_best + full[i] - best[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}