B3811
一扶苏一
·
·
题解
[语言月赛202307] 扶苏和串 题解
Source & Knowledge
2023 年 7 月语言月赛，由洛谷网校入门计划/基础计划提供。
本题考察枚举。。
文字题解
题目大意
给定一个数字矩阵，一次操作可以把所有数减去 1。问至少做多少次操作才能存在 k 个位置，使得该位置大于它所在的行和列元素之和。
### 解析
注意到当矩阵里的数都为负数时所有位置都满足要求。而至多 $\max a_i$ 次操作后矩阵里的数都会变成负数，所以答案不会超过 $\max a_i \leq 10^4$。
考虑枚举答案，从 $0$ 到 $10^4$ 枚举答案，每次先求出行和、列和，判定完成后，再给 $a_{i,j}$ 减去 $1$。
以下是求行和、列和的方法：
```cpp
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
row[i] += a[i][j];
col[j] += a[i][j];
}
}
```
接下来统计答案，用一个变量 $cnt$ 表示满足条件的格子个数，遍历一遍格子做统计：
```cpp
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (a[i][j] > row[i] + col[j]) ++cnt;
--a[i][j];
}
}
```
一旦 $cnt \geq k$，就可以停止枚举，输出答案，并退出。
```cpp
if (cnt >= k) {
std::cout << ans << std::endl;
return 0;
}
```
## 视频题解
