自动搬运

查看原文

来自洛谷，原作者为

	一扶苏一 休息结束。邮箱 yifusuyi@qq.com

搬运于2025-08-24 21:15:12，当前版本为作者最后更新于2020-12-01 09:39:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[语言月赛202307] 扶苏和串 题解

Source & Knowledge

2023 年 7 月语言月赛，由洛谷网校入门计划/基础计划提供。

本题考察枚举。。

文字题解

题目大意

给定一个数字矩阵，一次操作可以把所有数减去 $1$。问至少做多少次操作才能存在 $k$ 个位置，使得该位置大于它所在的行和列元素之和。

$1 \leq n, m \leq 100$，$1 \leq a_i \leq 10^4$。

解析

注意到当矩阵里的数都为负数时所有位置都满足要求。而至多 $\max a_i$ 次操作后矩阵里的数都会变成负数，所以答案不会超过 $\max a_i \leq 10^4$。

考虑枚举答案，从 $0$ 到 $10^4$ 枚举答案，每次先求出行和、列和，判定完成后，再给 $a_{i,j}$ 减去 $1$。

以下是求行和、列和的方法：

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$ 表示满足条件的格子个数，遍历一遍格子做统计：

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$，就可以停止枚举，输出答案，并退出。

if (cnt >= k) {
  std::cout << ans << std::endl;
  return 0;
}

视频题解