← 返回题目列表

AtCoder · arc180_b

B. 改进反转

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

分数: 600 点

问题陈述

给你一个排列 P=(P_1,P_2,\cdots,P_N) of (1,2,\cdots,N)。 另外,你会得到一个整数 K.

您可以执行以下操作零次或多次:

  • 选择整数 l 和 r (1 \leq l < r \leq N)。在这里,这一对 (l,r) 必须满足以下所有条件: 操作时的
    • K \leq r-l.
    • P_l > P_r 。
    • 这对 (l,r) 以前从未被选择过。
  • 然后,交换以下值 P_l 和 P_r.

您想要最大化操作数。 找到一种方法来实现这一目标。

约束

  • 2 \leq N \leq 500
  • 1 \leq K \leq N-1
  • (P_1,P_2,\cdots,P_N) 是一个排列 (1,2,\cdots,N).
  • 所有输入值均为整数。

输入

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

N K
P_1 P_2 \cdots P_N

输出

按以下格式打印答案:

m
l_1 r_1
l_2 r_2
\vdots
l_m r_m

在这里, m 是最大操作数,并且 l_i 和 r_i 的值 l 和 r 选择于 i分别进行第次操作。 如果存在多个解决方案,您可以打印其中任何一个。


示例输入 1

3 1
3 2 1

示例输出 1

3
2 3
1 3
1 2

在此示例中,最大操作数为 3。 示例输出中的操作进行如下:

  • 第一个操作:选择 (l,r)=(2,3)。我们有 之前没有选择过 1 \leq 3-2 和 P_2 > P_3,和 (2,3) ,因此满足条件。互换 P_2 和 P_3,导致 P=(3,1,2).
  • 第二次操作:选择 (l,r)=(1,3)。我们有 之前没有选择过 1 \leq 3-1 和 P_1 > P_3,和 (1,3) ,因此满足条件。互换 P_1 和 P_3,导致 P=(2,1,3).
  • 第三次操作:选择 (l,r)=(1,2)。我们有 之前没有选择过 1 \leq 2-1 和 P_1 > P_2,和 (1,2) ,因此满足条件。互换 P_1 和 P_2,导致 P=(1,2,3).

示例输入 2

5 4
1 4 3 2 5

示例输出 2

0

示例输入 3

4 2
4 1 2 3

示例输出 3

2
1 4
1 3

示例输入 4

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

示例输出 4

15
3 8
2 8
3 10
3 9
1 8
2 10
2 9
2 7
1 10
5 10
1 9
4 10
4 9
1 7
1 6