← 返回题目列表

AtCoder · arc204_b

B. 排序排列

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

分数: 800 点

问题陈述

给你正整数 N, K 和排列 P = (P_{1}, P_{2}, \dots, P_{NK}) of (1, 2, \dots, NK).

Alice 重复执行以下操作来排序 P 按升序排列。

  • 选择整数 i 和 j (i\neq j) 其中 1 \leq i, j \leq NK,并交换 P_{i} 和 P_{j}。如果 |i - j| 是的倍数 N,爱丽丝得到 1 点。

爱丽丝排序 P 按照最少的操作次数升序排列,在这种情况下,她获得的分数总和最大。

输出 Alice 获得的积分总和。

约束

  • 1\leq N\leq 500
  • 1\leq K\leq 10
  • (P_{1}, P_{2}, \dots , P_{NK}) 是一个排列 (1, 2, \dots, NK)
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N K
P_{1} P_{2} \dots P_{NK}

输出

输出答案。


示例输入 1

3 2
1 6 5 3 2 4

示例输出 1

2

例如, P 可以通过如下四种操作按升序排序。

  • 执行操作 (i, j) = (2, 5)。手术后, P = (1, 2, 5, 3, 6, 4).
  • 执行操作 (i, j) = (4, 6)。手术后, P = (1, 2, 5, 4, 6, 3).
  • 执行操作 (i, j) = (3, 5)。手术后, P = (1, 2, 6, 4, 5, 3).
  • 执行操作 (i, j) = (3, 6)。手术后, P = (1, 2, 3, 4, 5, 6).

在上述四个操作中,Alice 得到 1 点从每个 1圣和 4次操作,所以 Alice 总共得到 2 点。

这个操作序列是排序的方法之一 P 以最少的操作次数升序排列,并最大化该条件下的点数总和,因此输出 2.


示例输入 2

1 1
1

示例输出 2

0

示例输入 3

4 6
10 24 3 4 8 14 5 2 22 9 21 1 15 6 13 23 18 12 7 17 19 16 20 11

示例输出 3

7