4166. 遵循指令之意

【题目描述】

n 个食指传令官构成一个传令系统，第 i 个传令官的级别为 ai，ai 越低代表传令官级别越高，a 为 1 到 n 的排列。

可以对传令系统进行调整，调整方案为：选择一个下标 i(1 <= i <= n - 3)，然后分别调换 ai 和 a(i + 2)，a(i + 1) 和 a(i + 3)。

传令官需要对指令进行解读，因此靠前的传令官级别应该尽量高。

你需要对传令系统进行任意次调整，使得 a 的字典序最小。

形式化题意:

给定一个长度为 n 的排列，每次操作可以选定一个 [1, n - 3] 的下标 i，交换 ai, a(i +2), 然后交换 a(i + 1), a(i + 3)

求任意次操作以后能得到的最小的字典序 a。

【输入格式】

第一行一个整数 n 表示 n 个传令官

接下来一行 n 个数为 a1~an，a1~an 构成一个排列。

【输出格式】

输出任意次操作后字典序最小的 a。

【样例输入】

4
3 4 1 2

【样例输出】

1 2 3 4 

【样例输入】

5
5 4 3 1 2

【样例输出】

2 1 3 4 5 

【样例说明】

第一个样例中，选择下标 1 进行一次调整。

第二个样例中，先选择下标 2 进行调整变成 5 1 2 4 3

再选择下标 1 进行调整，变成 2 4 5 1 3

再选择下标 2 进行调整，变成 2 1 3 4 5

大样例

【数据规模与约定】

对于 10% 的数据 保证奇数位置形成的序列和偶数位置形成的序列逆序对个数奇偶性不同, n <= 10

对于 60% 的数据 n <= 5000

对于 100% 的数据 n <= 1000000

【来源】

CodeForces （Problem - 2101B - Codeforces，题面有修改） 

原题链接