← 返回题目列表

Codeforces · 1294/E

E. 获得排列

中文机器翻译题面 查看原题

给定一个大小为 $$$n \times m$$$ 的矩形矩阵,由从 $$$1$$$ 到 $$$2 \cdot 10^5$$$ 的整数组成。

只需一招,您就可以:

- 选择矩阵的任何元素并将其值更改为 $$$1$$$ 和 $$$n \cdot m$$$ 之间的任何整数(含);
- 取任意列并将其循环上移一个单元格(请参阅下面此类循环移位的示例)。

循环移位是一种操作,您可以选择一些 $$$j$$$ ($$$1 \le j \le m$$$) 并同时设置 $$$a_{1, j} := a_{2, j}, a_{2, j} := a_{3, j}, \dots, a_{n, j} := a_{1, j}$$$。

第一列循环移位示例

您想要执行最少的移动次数以使该矩阵看起来像这样:

换句话说,目标是获得矩阵,其中 $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ (即 $$$a_{i, j} = (i - 1) \cdot m + j$$$)执行的移动次数最少。

输入

输入的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^5, n \cdot m \le 2 \cdot 10^5$$$) — 矩阵的大小。

接下来的 $$$n$$$ 行每行包含 $$$m$$$ 个整数。 $$$i$$$ 行和 $$$j$$$ 位置处的数字为 $$$a_{i, j}$$$ ($$$1 \le a_{i, j} \le 2 \cdot 10^5$$$)。

输出

打印一个整数 — 获得矩阵所需的最少移动次数,其中 $$$a_{1, 1} = 1, a_{1, 2} = 2, \dots, a_{1, m} = m, a_{2, 1} = m + 1, a_{2, 2} = m + 2, \dots, a_{n, m} = n \cdot m$$$ ($$$a_{i, j} = (i - 1)m + j$$$)。

示例

输入 #1

3 3
3 2 1
1 2 3
4 5 6

输出 #1

6

输入 #2

4 3
1 2 3
4 5 6
7 8 9
10 11 12

输出 #2

0

输入 #3

3 4
1 6 3 4
5 10 7 8
9 2 11 12

输出 #3

2

注意

在第一个示例中,您可以设置 $$$a_{1, 1} := 7, a_{1, 2} := 8$$$ 和 $$$a_{1, 3} := 9$$$,然后循环移动第一列、第二列和第三列,因此答案为 $$$6$$$。可以证明你无法得到更好的答案。

在第二个示例中,矩阵已经很好,因此答案是 $$$0$$$。

在第三个例子中,将第二列循环移位两次就足以获得一个好的矩阵,所以答案是$$$2$$$。