CF2121C Those Who Are With Us
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;
}