CF2121C Those Who Are With Us - 洛谷

题目描述
给定一个有 n 行 m 列的整数矩阵。第 i 行第 j 列的单元格包含数字 ai,j​。
你可以恰好进行一次如下操作：

• 选择两个数 1≤r≤n 和 1≤c≤m。
• 对于矩阵中所有满足 i=r 或 j=c 的单元格 (i,j)，将 ai,j​ 减去 1。
  你需要在恰好进行一次这样的操作后，求出矩阵 a 中可能的最小最大值。

输入格式
每组测试数据包含多组测试用例。第一行包含一个整数 t（1≤t≤104），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含两个整数 n 和 m（1≤n,m≤103），表示矩阵的行数和列数。
接下来的 n 行，每行包含 m 个整数 ai1​,ai2​,…,aim​（1≤aij​≤100），表示矩阵 a 的元素。
保证所有测试用例中 n⋅m 的总和不超过 2×105。

输出格式
对于每个测试用例，输出一次操作后矩阵 a 中的最小最大值。

输入输出样例
输入 #1
10
1 1
1
1 2
1
1 2
2 1
2
2 1
2 3
2 2
4 2
3 4
1 2 3 2
3 2 1 3
2 1 3 2
4 3
1 5 1
3 1 3
5 5 5
3 5 1
4 4
1 3 3 2
2 3 2 2
1 2 2 1
3 3 2 3
2 2
2 2
1 2
3 2
1 2
2 1
1 2
1 2
3 3
2 1 1
1 2 1
1 1 2

输出 #1
0
1
1
2
3
2
4
3
1
1

说明 / 提示
在前三个测试用例中，你可以选择 r=1 且 c=1。
在第四个测试用例中，你可以选择 r=1 且 c=2。
在第五个测试用例中，你可以选择 r=2 且 c=3。
在第六个测试用例中，你可以选择 r=3 且 c=2。
由 ChatGPT 4.1 翻译

思路：
找出最大值，计算每一行每一列的最大值个数，这样方便找出十字型内是否包含所有最大值。

代码：
 

#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n + 1, vector<int>(m + 1));
        int max_num = -1;
        
        // 第一步：找出最大值
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                cin >> a[i][j];
                max_num = max(max_num, a[i][j]);
            }
        }
        
        // 第二步：统计每行、每列的最大值数量，以及总数量
        vector<int> row_count(n + 1, 0);  // 每行的最大值数量
        vector<int> col_count(m + 1, 0);  // 每列的最大值数量
        int total = 0;                    // 最大值的总数量
        
        for (int i = 1; i <= n; ++i) 
		{
            for (int j = 1; j <= m; ++j) 
			{
                if (a[i][j] == max_num)
				 {
                    row_count[i]++;
                    col_count[j]++;
                    total++;
                }
            }
        }
        
        // 第三步：判断是否存在一个十字能包含所有最大值
        bool exists = false;
        for (int i = 1; i <= n; ++i) 
		{
            for (int j = 1; j <= m; ++j) 
			{
                // 当前位置是否是最大值（用于去重）
                int overlap = (a[i][j] == max_num) ? 1 : 0;
                // 十字包含的最大值数量 = 行数量 + 列数量 - 重复计算的当前位置
                if (row_count[i] + col_count[j] - overlap == total) 
				{
                    exists = true;
                    break;
                }
            }
            if (exists) break;
        }
        
        // 输出结果
        if (exists) {
            cout << max_num - 1 << '\n';
        } else {
            cout << max_num << '\n';
        }
    }
    return 0;
}