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

【题目描述】

有一个$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$,表示最少需要改变的数的个数。

【样例输入】

4



1 1 3 4



5 1 1 8



9 10 1 1



1 14 15 1

【样例输出】

2

【样例解释】

把矩阵改成

$$\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$