分数: 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