关于好网格的近10条评论(全部评论)

2754. [济南集训2017] 好网格

★★★ 输入文件：goodsquare.in 输出文件：goodsquare.out 简单对比
时间限制：1 s 内存限制：512 MiB

有一个 $n \times n$ 的网格图,其中每个格子都有一个数。

设 $A_i$ 为第i行的最小值, $B_i$ 为第 $i$ 列的最大值,我们称一个网格是好的,当

且仅当满足

$\max(A_1 ,\cdots , A_n ) = \min(B_i , \cdots, B_n )$

现在问最少改变多少个数可以使得这个网格是好的。

第一行一个整数 $n$ 。

之后 $n$ 行,每行 $n$ 个数,描述这个矩阵。

一个数 $ans$ ,表示最少需要改变的数的个数。

1 1 3 4

5 1 1 8

9 10 1 1

1 14 15 1

把矩阵改成

$\begin{array}{}1&1&3&4\\5&1&1&8\\9&10&10&10\\1&14&15&1\\\end{array}$

即满足题目要求

对于 $30\%$ 的数据, $1 ≤ n, a_i ≤ 10$

对于另外 $30\%$ 的数据, $1 ≤ n ≤ 100, 1 ≤ a_i ≤ 3$

对于 $90\%$ 的数据, $1 ≤ n ≤ 100, 1 ≤ a_i ≤ 10^5$

对于 $100\%$ 的数据, $1 ≤ n ≤ 1000, 1 ≤ a_i ≤ 10^9$

清北学堂济南NOIP集训二试 $T_3$