传送门：洛谷 CF2121C Those Who Are With Us | Codeforces C. Those Who Are With Us

更佳的阅读体验：CF2121C 题解

简要题意：给定一个 $n \times m$ 整数矩阵 $a$，执行恰好一次操作：选择一行和一列，将该行和该列的所有元素各减一（交叉点只减一次）。求操作后矩阵中最大值的最小可能值。

给出一个较为暴力的解法。

尽管本题要求输入一个矩阵，但本题有 $n, m \le 10^5$，开一个每一维大小都是 $10^5$ 的数组显然不现实。但因为有 $n \times m \le 10^5$，我们可以将整个矩阵线性地存储下来。

我们设整个矩阵的最大值为 $a_{\max}$。那么如果操作能覆盖所有值为 $a_{\max}$ 的元素（每个 $a_{\max}$ 至少被行操作或列操作覆盖一次），那么操作后最大值就会变成 $a_{\max}-1$；否则，操作后最大值仍然是 $a_{\max}$。

因此，问题转化为寻找一个行和列的组合，使得它们的并集能够覆盖尽可能多的 $a_{\max}$，从而最小化操作后的最大值。

我们记录矩阵中的最大值 $a_{\max}$，并统计每行每列中值为 $a_{\max}$ 的元素个数。因为 $n \times m \le 10^5$，所以只要暴力地枚举所有可能的行和列的组合 $(i, j)$ 即可。枚举时计算选择 $(i,j)$ 能覆盖的 $a_{\max}$ 的数量，我们记录能覆盖最多 $a_{\max}$ 的行和列的组合 $(r,c)$。

确定最优位置后，可以直接按题意模拟。将第 $r$ 行的所有元素减一，第 $c$ 列的所有元素减一，再将交叉点加一修正。最后输出操作后矩阵的最大值即可。

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 10, INF = 1e9;
int t, n, m, a[N], cntr[N], cntc[N], r, c, maxn, minn;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    for (cin >> t; t; --t) {
        maxn = 0, minn = INF, r = c = 0;
        fill(cntr + 1, cntr + n + 1, 0);
        fill(cntc + 1, cntc + m + 1, 0);
        cin >> n >> m;
        for (int i = 1; i <= n * m; ++i) {
            cin >> a[i];
            maxn = max(maxn, a[i]), minn = min(minn, a[i]);
        } for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                if (a[(i - 1) * m + j] == maxn) ++cntr[i], ++cntc[j];
        int res = 0;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                int tot = cntr[i] + cntc[j] - (a[(i - 1) * m + j] == maxn);
                if (tot > res) res = tot, r = i, c = j;
            }
        for (int i = 1; i <= m; ++i) --a[(r - 1) * m + i];
        for (int i = 1; i <= n; ++i) --a[(i - 1) * m + c];
        ++a[(r - 1) * m + c];
        cout << *max_element(a + 1, a + n * m + 1) << '\n';
    }
}