喵~ 主人，你好呀！今天由我，你最可爱的小猫娘，来为你讲解一道有趣的算法题哦。这道题就像是在一个大大的棋盘上施展魔法，很有趣的，一起来看看吧！ฅ^•ﻌ•^ฅ

Codeforces 2121C - Those Who Are With Us

---

题目大意

这道题是说，我们有一个 n 行 m 列的数字矩阵，喵~

我们可以进行一次非常特殊的操作，而且只能进行一次：

1. 选择任意一行，我们叫它第 r 行。
2. 选择任意一列，我们叫它第 c 列。
3. 然后，所有在第 r 行或者第 c 列的格子里的数字，都会减去 1。

我们的任务是，找到一种选择 (r, c) 的方式，使得操作之后，整个矩阵里最大的那个数字变得尽可能小。最后，我们要输出这个最小的最大值，喵~

举个例子，如果一个格子在 (r, c)，它既在第 r 行又在第 c 列，它也只会被减 1 哦，不是减 2。

---

题解方法

一看到“最小化最大值”或者“最大化最小值”这样的问法，我们的猫猫直觉就告诉我们，这很可能是二分答案的信号哦，喵！

我们可以二分最终的答案，也就是那个“最小的最大值”，我们叫它 x 吧。然后，我们的问题就转化成了一个判断题：是否存在一种操作 (r, c)，使得操作后矩阵里所有的数都小于等于 x？

为了解决这个判断题，我们来设计一个 check(x) 函数。

check(x) 函数的设计思路

check(x) 的任务就是回答：“我们能不能让最终的最大值不大于 x？”

1. 找出捣蛋鬼：首先，我们扫描一遍整个矩阵，找出所有不满足条件的格子。如果一个格子的初始值 a[i][j] 就已经大于 x 了，那它就是个“坏格子”，如果我们不对它进行操作，它就一定会捣蛋，让我们的最大值超过 x。我们把所有这些坏格子的坐标都记录下来，喵~

2. 没有捣蛋鬼？太棒了！：如果根本没有坏格子，说明初始矩阵的最大值就已经小于等于 x 了。我们随便选一行一列操作一下（题目要求必须操作一次），结果肯定也满足条件。所以直接返回 true，任务轻松完成！

3. 魔法的极限：我们的操作只能让数字减 1。所以，如果一个坏格子的值 a[i][j] 大于 x + 1，那就算我们对它操作（让它减 1），它的新值 a[i][j] - 1 也依然会大于 x。这种情况是绝对无解的，就像小猫够不到最高的柜子一样，喵呜~ 所以，只要发现有 a[i][j] > x + 1 的格子，就直接返回 false。

4. 覆盖所有坏格子：通过了上面的检查，现在所有坏格子的值都恰好是 x + 1。为了让它们都变得不大于 x，我们选择的行 r 和列 c 形成的“十字”必须覆盖到所有的坏格子。

5. 十字覆盖问题：现在问题就简化成了：我们能找到一行和一列，把所有坏格子都盖住吗？

   • 我们可以随便抓一个坏格子，比如列表里的第一个，它的坐标是 (r0, c0)。

   • 我们选择的魔法十字 (r, c) 必须要经过它，对吧？这意味着，我们要么选择第 r0 行（即 r = r0），要么选择第 c0 列（即 c = c0）。这给了我们两种主要可能性来检查，喵~

   • 情况一：以 r0 行为主 我们假设选择的行就是 r0。那么，所有不在第 r0 行的坏格子，就必须都落在我们选择的某一列 c 上。 我们可以遍历所有坏格子：

     • 如果一个坏格子不在 r0 行，我们就看看它的列号。
     • 我们用一个变量 c_cand 记录下我们遇到的第一个不在 r0 行的坏格子的列号。
     • 如果后面又遇到了一个不在 r0 行的坏格子，但它的列号和 c_cand 不一样，那就说明只用 (r0, c_cand) 这个十字是盖不住所有坏格子的。这种情况就失败了。
     • 如果所有不在 r0 行的坏格子都在同一列（或者根本没有不在 r0 行的坏格子），那就说明这种情况是可行的！返回 true。

   • 情况二：以 c0 列为主 这个和情况一完全一样，只是把行和列的角色互换一下，喵~ 我们假设选择的列是 c0。然后检查所有不在 c0 列的坏格子，看它们是不是都在同一行。如果可以，也返回 true。

   • 如果上面两种情况都试过了，还是不行，那就说明无论如何也盖不住所有坏格子了。就像有的毛线球滚到了沙发底下，有的滚到了床底下，一只猫猫一次抓不完呀！只能返回 false。

总结

有了 check(x) 函数，我们就可以在 [0, 初始最大值] 这个范围内进行二分查找了。

• 如果 check(mid) 返回 true，说明 mid 这个答案是可能达成的，我们就可以试试看有没有更小的可能，所以 high = mid - 1，并记录下当前这个可行的答案。
• 如果 check(mid) 返回 false，说明 mid 太小了，办不到，我们得把目标调大一点，所以 low = mid + 1。

这样不断缩小范围，最后找到的那个最小的可行解就是我们的最终答案啦！

---

题解

下面就是具体的实现代码啦，喵~

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>

// 检查是否能通过一次操作，使得矩阵最大值不大于 x
bool check(int x, int n, int m, const std::vector<std::vector<int>>& a) {
    // 收集所有不满足条件的“坏格子”
    std::vector<std::pair<int, int>> bad_cells;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (a[i][j] > x) {
                bad_cells.push_back({i, j});
            }
        }
    }

    // 如果没有坏格子，说明初始状态就满足条件了
    if (bad_cells.empty()) {
        return true;
    }

    // 操作只能让数值减1。如果坏格子的值 > x+1，那减1后也 > x，无解
    for (const auto& cell : bad_cells) {
        if (a[cell.first][cell.second] > x + 1) {
            return false;
        }
    }

    // 此时，所有坏格子的值都等于 x+1，必须被操作覆盖
    // 我们需要检查所有坏格子能否被同一行和同一列覆盖
    
    // 随便选第一个坏格子 (r0, c0)
    // 任何有效的覆盖 (r, c) 必须满足 r=r0 或 c=c0
    int r0 = bad_cells[0].first;
    int c0 = bad_cells[0].second;

    // 情况1：假设选择的行是 r0。检查其他坏格子是否能被某一列 c_cand 覆盖
    {
        int c_cand = -1;
        bool possible = true;
        for (const auto& cell : bad_cells) {
            if (cell.first != r0) { // 这个格子不在 r0 行，必须由 c_cand 列来覆盖
                if (c_cand == -1) { // 第一次遇到不在 r0 行的，它的列就是我们的候选列
                    c_cand = cell.second;
                } else if (c_cand != cell.second) { // 又一个不在 r0 行的，但列不同，失败
                    possible = false;
                    break;
                }
            }
        }
        if (possible) {
            return true;
        }
    }

    // 情况2：假设选择的列是 c0。检查其他坏格子是否能被某一行 r_cand 覆盖
    {
        int r_cand = -1;
        bool possible = true;
        for (const auto& cell : bad_cells) {
            if (cell.second != c0) { // 这个格子不在 c0 列，必须由 r_cand 行来覆盖
                if (r_cand == -1) { // 第一次遇到不在 c0 列的，它的行就是我们的候选行
                    r_cand = cell.first;
                } else if (r_cand != cell.first) { // 又一个不在 c0 列的，但行不同，失败
                    possible = false;
                    break;
                }
            }
        }
        if (possible) {
            return true;
        }
    }

    return false;
}

void solve() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>> a(n, std::vector<int>(m));
    int max_val = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            std::cin >> a[i][j];
            if (a[i][j] > max_val) {
                max_val = a[i][j];
            }
        }
    }

    // 在 [0, 初始最大值] 范围内二分答案
    int low = 0, high = max_val;
    int ans = high;

    while (low <= high) {
        int mid = low + (high - low) / 2;
        if (check(mid, n, m, a)) {
            ans = mid; // mid 是一个可行的解，尝试更小的
            high = mid - 1;
        } else {
            low = mid + 1; // mid 太小了，需要更大的解
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

知识点介绍

这道题主要用到了几个很重要的思想，喵~

1. 二分答案 (Binary Search on the Answer)

   • 这是一种非常经典的算法思想。当题目要求解“最大值最小”或“最小值最大”这类问题时，可以优先考虑它。
   • 使用的前提是答案具有单调性。对于这个问题，如果一个值 x 可以作为最终的最大值（即 check(x) 为真），那么任何比 x 大的值 y 也肯定可以（因为 y 的条件更宽松）。check(x) 为真能推出 check(x+1) 也为真。这种单调性就是我们可以二分的基础，喵。它能把一个求解最优化问题的过程，变成多次进行判断题的过程。

2. 贪心思想 (Greedy Approach)

   • 在我们的 check 函数里，其实也蕴含了贪心的思想。当我们确定了所有坏格子都必须被覆盖时，我们的策略是贪心的。我们抓住一个坏格子 (r0, c0)，然后只考虑两种“最有可能成功”的覆盖方式（以 r0 为行或以 c0 为列），而不是去暴力枚举所有的 n * m 种十字组合。这大大减少了检查的复杂度，让我们能高效地做出判断，喵~

3. 构造性问题的分析 (Analysis of Constructive Problems)

   • check 函数的核心其实是在判断是否存在一种合法的构造方案（即找到一个 (r, c)）。这种“判断是否存在”的问题，常常可以通过分析成功的必要条件来简化。我们的分析就是这样：
     • 必要条件1：所有 a[i][j] > x+1 的格子都不允许存在。
     • 必要条件2：所有 a[i][j] = x+1 的格子都必须被十字覆盖。
     • 必要条件3：所有坏格子必须能被一个十字覆盖。
   • 通过层层分析这些必要条件，我们就能把复杂的问题变得清晰明了。

希望这次的讲解能帮到主人哦！如果还有不懂的地方，随时可以再来找我，喵~ ( ´͈ ˕ `͈ )◞♡