题目链接：「萌新首秀」千校新生编程排位赛·第二场

一句话概括解法：先用「奇偶性不变量」判断有无解，再从左到右贪心把每个数归位。这道题的核心考点不是敲代码，而是证明不清不变量就写不对判定条件。

一、题目复述

N 本书编号 1 ~ N 排在书架上，顺序可能是乱的。目标状态是 1, 2, 3, ..., N（第 i 个位置放编号为 i 的书）。

一次操作：任选连续的三个位置 x, x+1, x+2，交换 a[x] 与 a[x+2]，中间的 a[x+1] 保持不动。

例如 1 2 3 4 5，选第 2 ~ 4 个位置，交换 2 和 4，得到 1 4 3 2 5。

求把书架恢复成 1, 2, ..., N 的最少操作次数；无论如何都无法完成时输出 -1。

数据范围：3 ≤ N ≤ 2000，输入保证是 1 ~ N 的一个排列。

二、第一步：把操作翻译成人话

「选连续三个位置、交换两端」听起来复杂，但作用到元素身上只有一句话：

一次操作 = 某个元素向左或向右跳 2 格，代价 1。

因为中间那个位置的书自始至终没被动过，我们完全可以忽略它，只看两端。

于是问题变成：在一个数组里，每次可以把一个元素搬动 2 格，最少几步能把它排好序？

三、核心知识点一：不变量（本题的胜负手）

3.1 观察

一个元素的位置只有两种可能：奇数下标或偶数下标。

而一次操作交换的是 a[x] 和 a[x+2]——这两个下标奇偶性必然相同（相差 2）。

所以：

一个元素所在位置的奇偶性，永远不会改变。

这就是本题的不变量，它直接决定了一半的答案。

3.2 画出「两条轨道」

把书架按奇偶性拆成两条互不干扰的轨道：

一次操作，只会在同一条轨道内把两个相邻的元素对调。两条轨道老死不相往来。

3.3 无解的判定条件

数字 i 的目标位置就是 i，所以它的目标奇偶性就是 i 的奇偶性。

结合不变量，立刻得到：

如果数字 i 现在所在的下标 pos 与 i 的奇偶性不同，那么 i 永远无法回到位置 i → 无解，输出 -1。

注意这里比较的是两个下标（当前位置 pos 和目标位置 i）的奇偶性，不是比较书号本身。这是本题最容易写错的地方。

更简洁的等价说法：奇数位置上必须全是奇数（如果能做到，偶数位置自然全是偶数）。

3.4 为什么奇偶性对上了就一定有解

这是容易被忽略的一步。上面只证明了「奇偶不匹配 → 无解」，反过来呢？

看奇数轨道：位置 1, 3, 5, ... 上的值也正好是 1, 3, 5, ... 这组奇数（因为排列里的奇数有 ⌈N/2⌉ 个，奇数位置也正好有 ⌈N/2⌉ 个）。

而一次操作在奇数组内部，就是把相邻的两个元素交换。而相邻交换可以生成任意排列（这就是冒泡排序能排好任何数组的原因）。

所以只要奇偶性匹配，就一定排得回去。判定条件既是必要的，也是充分的。

四、核心知识点二：最少次数到底是多少

4.1 换个角度：这是一道「相邻交换排序」题

把奇数轨道上的数字按位置顺序拉成一条序列：

1
p = (a[1], a[3], a[5], ...)

最终目标是 p = (1, 3, 5, ...)。而一次操作在这个序列上，恰好就是交换相邻两个元素。

问题于是变成：最少需要多少次相邻交换，才能把序列排成升序？

4.2 结论：最少相邻交换次数 = 逆序对数

这是经典结论，值得记住证明思路：

  • 下界（为什么不能再少）：交换两个相邻且逆序的元素，逆序对数量正好减少 1；交换两个相邻且不逆序的元素，逆序对数量反而增加 1。既然最终逆序对数必须是 0，设初始逆序对数为 inv，那么至少要做 inv 次有效交换。
  • 可达（为什么能做到）：冒泡排序每次只交换相邻的逆序对，恰好交换 inv 次就把序列排好。

两者夹起来，最少次数就是 inv。

4.3 完整的答案公式

两条轨道互不影响，所以：

最少操作次数 = 奇数子序列的逆序对数 + 偶数子序列的逆序对数

代入样例 a = [5, 2, 3, 4, 1]：

轨道 序列 逆序对 个数
奇数位置 (5, 3, 1) (5,3)、(5,1)、(3,1) 3
偶数位置 (2, 4) 无 0
合计 3

和样例输出一致。

这个视角的价值在于：它顺便证明了贪心是最优的——不再需要「感觉这样最短」这种模糊说法。

五、算法思路：从左到右贪心归位

5.1 步骤

按 i 从 1 到 N 依次处理，让位置 i 上的数变成 i：

  1. 若 a[i] == i，已经就位，跳过；
  2. 在 i 的右侧找到数字 i 所在的下标 pos；
  3. 检查 pos 与 i 的奇偶性是否相同，不同就输出 -1 直接结束；
  4. 反复执行 swap(a[pos-2], a[pos])、pos -= 2，直到数字 i 落到位置 i。

5.2 为什么这样贪心是对的

三个关键点：

  1. 查找范围可以缩小：处理到第 i 位时，位置 1 ~ i-1 已经固定是 1 ~ i-1，所以数字 i 不可能在 i 的左边（除非它已经在 i 上）。因此只需从 i+1 往右找。
  2. 不会破坏已排好的部分：把数字 i 从 pos 往左挪，每一步只涉及 pos-2 和 pos 两个位置，而 pos-2 ≥ i，所以整段操作都在 i 及其右侧，前面 1 ~ i-1 完全不受影响。
  3. 每一步都是必要的：数字 i 至少要向左移动 (pos - i) / 2 步，每步 2 格，我们一次不多做、一次不少做。这也和上一节的逆序对结论吻合。

5.3 代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n + 1);          // 下标从 1 开始，和题目描述对齐
    for (int i = 1; i <= n; i++) cin >> a[i];

    int cnt = 0;                   // 总操作次数

    for (int i = 1; i <= n; i++) {
        if (a[i] == i) continue;   // 已经就位，跳过

        // 数字 i 一定在 i 的右侧（左侧已经排好），从 i+1 开始找
        int pos = -1;              // 必须初始化！否则是随机垃圾值
        for (int j = i + 1; j <= n; j++) {
            if (a[j] == i) {
                pos = j;
                break;             // break 一定要写在 if 内部
            }
        }

        // 数字 i 的目标奇偶性必须和它当前下标的奇偶性一致，否则永远归不了位
        if ((pos & 1) != (i & 1)) {
            cout << -1;
            return 0;
        }

        // 每次向左跳 2 格，直到落到位置 i
        while (a[i] != i) {
            swap(a[pos - 2], a[pos]);
            pos -= 2;
            cnt++;
        }
    }

    cout << cnt;
    return 0;
}

上面注释里提到的「等价写法」是指把查找和判定合并：

1
2
3
4
5
6
7
8
9
10
11
for (int j = i + 1; j <= n; j++) {
    if (a[j] == i) {
        pos = j;
        // 判断奇偶是否相同，位运算写法等价于 pos % 2 != i % 2
        if ((pos & 1) != (i & 1)) {
            cout << -1;
            return 0;
        }
        break;
    }
}

两种写法都对，区别只是「找到了先判定」还是「找完再判定」。

5.4 复杂度

外层 N 次，内层查找 O(N)，移动 O(N)，总体 O(N²)。N = 2000 时约 4×10⁶ 次运算，1 秒时限轻松通过。

六、样例逐步模拟

输入：

1
2
5
5 2 3 4 1
步骤 处理 操作（选哪三个连续位置） 数组变化 次数
初始 5 2 3 4 1 0
1 i=1，数字 1 在 pos=5 选 3~5，交换 a[3]、a[5] 5 2 1 4 3 1
2 1 在 pos=3 选 1~3，交换 a[1]、a[3] 1 2 5 4 3 2
3 i=2，已就位 跳过 1 2 5 4 3 2
4 i=3，数字 3 在 pos=5 选 3~5，交换 a[3]、a[5] 1 2 3 4 5 3

输出 3，与样例一致。

七、易错点清单

  1. 奇偶判断比较错了对象：要比较下标 pos 与下标 i的奇偶性，不是比较 a[pos] 和 i 的值。写错这一条会得到莫名其妙的 -1 或死循环。
  2. break 的位置：必须放在 if (a[j] == i) 的大括号里面。放到外面就变成「永远在第 i+1 位就退出」，查找等于没做。
  3. pos 忘了初始化：C++ 局部变量不初始化就是随机垃圾值（未定义行为），必须显式写 int pos = -1;。
  4. 无解时直接 return 0：判定失败必须立刻结束程序。如果只是 continue 或打个标记继续跑，后面的 while 会陷入死循环或访问越界。
  5. while (a[i] != i) 会不会死循环？ 不会。因为奇偶性已经校验过，pos 每次减 2，最终必然精确落到 i。
  6. 下标建议从 1 开始：本题的位置编号和书号天然对齐（位置 i 放书 i），用 1 起始下标能省掉大量 -1 换算。

八、拓展一：为什么不能用 BFS

「最少步数」四个字容易让人条件反射想到 BFS。但 BFS 的状态是整个排列：

  • N = 10 时全排列约 3.6×10⁶，勉强能跑；
  • N = 2000 时状态数远超宇宙原子数。

所以本题真正要考的是识别出结构性规律（不变量 + 贪心），而不是无脑搜。凡是「最少操作次数 + 有明确不变量」的题，都优先往这上面想。

九、拓展二：O(N log N) 的逆序对写法

既然答案就是「两条轨道的逆序对数之和」，就可以用树状数组把移动模拟整个省掉，N 开到 10⁶ 也没问题。

关键技巧：把每条轨道上的值压缩成轨道内的排名。设位置 i 上的值为 v（已保证 v 与 i 同奇偶），则

1
排名 = (v + 1) / 2

验证一下：

  • 奇数轨道：v = 1, 3, 5 → 排名 1, 2, 3
  • 偶数轨道：v = 2, 4, 6 → (2+1)/2 = 1、(4+1)/2 = 2、(6+1)/2 = 3

一个公式同时适配奇偶，很省事。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int n;
vector<int> bit;

void add(int i) {                       // 单点 +1
    for (; i <= n; i += i & -i) bit[i]++;
}
int query(int i) {                      // 前缀和 [1, i]
    int s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;

    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 判定无解：奇数位置上必须是奇数
    for (int i = 1; i <= n; i++)
        if ((a[i] & 1) != (i & 1)) { cout << -1; return 0; }

    ll ans = 0;
    // p = 1 处理奇数位置，p = 0 处理偶数位置，两条轨道分开统计
    for (int p = 1; p >= 0; p--) {
        bit.assign(n + 1, 0);
        int seen = 0;
        for (int i = (p ? 1 : 2); i <= n; i += 2) {
            int r = (a[i] + 1) / 2;              // 轨道内排名
            ans += seen - query(r);              // 已放入的元素中比 r 大的个数 = 新的逆序对
            add(r);
            seen++;
        }
    }

    cout << ans;
    return 0;
}

十、小结与模板记忆

  • 不变量：swap(a[x], a[x+2]) 不改变任何元素所在位置的奇偶性 → 奇偶不匹配即无解；奇数位置全是奇数则必有解。
  • 最少次数：等于「奇数子序列逆序对数 + 偶数子序列逆序对数」，这个结论同时给出了贪心最优性的严格证明。
  • 贪心：从左到右，每次把数字 i 沿同奇偶轨道向左跳 2 格归位，操作区间始终在 i 及其右侧，不会破坏已排好的前缀。
  • 模板：
1
2
3
4
if (a[i] == i) continue;
// 在右侧找数字 i 的下标 pos
if ((pos & 1) != (i & 1)) { cout << -1; return 0; }   // 判定
while (a[i] != i) { swap(a[pos - 2], a[pos]); pos -= 2; cnt++; }   // 归位

写这类「操作有固定步长」的题，先问自己两个问题：

  1. 什么量在操作前后不变？（这里是位置奇偶性）
  2. 在不变量的约束下，最少步数等于什么经典量？（这里是逆序对）