CF2248F Matrix Elimination

给定一个整数 $k$ 和一个 $n$ 行 $m$ 列的矩阵 $v$，其中第 $i$ 行第 $j$ 列的元素记为 $v_{i,j}$。 如果某个格子 $(x, y)$ 的值大于等于第 $x$ 行和第 $y$ 列中其他所有格子的值之和，则称其为一个峰值格。形式化地说，如果满足： $$ v_{x,y} \ge \sum_{\substack{1 \le i \le n \\ i \neq x}} v_{i,y} + \sum_{\substack{1 \le j \le m \\ j \neq y}} v_{x,j}. $$ 你可以进行任意次（包括 0 次）如下操作： - 选择四个整数 $x_l$、$x_r$、$y_l$、$y_r$（$1 \le x_l \le x_r \le n$，$1 \le y_l \le y_r \le m$）。 - 对所有满足 $x_l \le i \le x_r$ 且 $y_l \le j \le y_r$ 的 $v_{i,j}$ 元素减去 $1$。 请你求出最少要进行多少次操作，才能使矩阵中至少有 $k$ 个峰值格。

每个测试点包含若干组测试数据。第一行为测试数据组数 $t$（$1 \le t \le 10^4$）。每组数据描述如下： 每组的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n, m \le 10^5$，$1 \le k \le n \cdot m$，且 $n \cdot m \le 10^5$）——表示矩阵的行数、列数和需要的峰值格数量。 接下来 $n$ 行，每行有 $m$ 个整数 $v_{i,1}, v_{i,2}, \ldots, v_{i,m}$（$-10^9 \le v_{i,j} \le 10^9$）。 保证所有测试数据的 $n \cdot m$ 之和不超过 $10^5$。

对于每组测试数据，输出一个整数，表示最少操作次数以获得至少 $k$ 个峰值格。 如果无解，则输出一个整数 $-1$。

对于第一个测试点，你可以进行如下两个操作： - 选择 $(x_l, x_r, y_l, y_r) = (1, 3, 2, 3)$； - 选择 $(x_l, x_r, y_l, y_r) = (2, 3, 1, 3)$。 操作后矩阵变为： $\color{green}{-1}$ $-31$ $\color{green}{6}$ $5$ $\color{green}{-5}$ $\color{green}{20}$ $\color{green}{0}$ $\color{green}{-20}$ $\color{green}{14}$，绿色部分为 7 个峰值格。例如： - 格子 $(1, 1)$ 是峰值格，因为 $-1 \ge 5 + 0 - 31 + 6 = -20$； - 格子 $(3, 1)$ 是峰值格，因为 $0 \ge -20 + 14 - 1 + 5 = -2$； - 格子 $(2, 1)$ 不是峰值格，因为 $5 < -5 + 20 - 1 + 0 = 14$。 可以证明，少于两次操作无法达到 7 个峰值格，因此答案为 $2$。 第八组数据中，唯一的元素值为 $-5$。$1 \times 1$ 矩阵中只有当唯一一个元素非负时，该格子才能为峰值格。但每一次操作只能使其值减小，因此不可能使其成为峰值格。 最后一个测试点，两个格子都成为峰值格当且仅当它们的值相等。因此，第一个格子需要从 $10^9$ 降到 $-10^9$，共需要 $2 \times 10^9$ 次操作。 由 ChatGPT 5 翻译