1. 题目理解与核心思路

1.1 先别急着写代码，把操作本质看懂

这道题一上来给出的操作看起来很简单：选两个相邻的元素，如果它们的和是奇数，就交换它们的位置。很多新手看到这里容易产生一个直觉——这不就是冒泡排序的变种吗，直接模拟就行了。但如果你真的去模拟，十有八九会在第 20 个测试点超时，或者在某个隐蔽的边界情况上 WA 到怀疑人生。因为题目的关键根本不在“怎么模拟交换”，而是在“这个操作到底能改变什么、不能改变什么”。

那两个数的和是奇数，意味着什么？想想奇偶性的基本规则：奇数加奇数等于偶数，偶数加偶数等于偶数，只有奇数加偶数（或者反过来）才等于奇数。所以这个操作的真正含义是——只有当两个相邻元素的奇偶性不同时，才能交换它们。换句话说，一个奇数和它相邻的偶数可以互换位置，但两个奇数之间、两个偶数之间，永远不可能通过这个操作直接交换。

这个观察是整个题目的分水岭。后面所有结论都建立在它之上。你要是没想透这一点，后面看官方题解的讨论区间、讨论逆序对，都会觉得莫名其妙。

1.2 这个限制条件藏着整个问题的解法

有了“只有奇偶性不同的相邻元素才能交换”这个前提，接下来的问题就是：那我能通过一系列操作，把序列变成什么样？

举个例子，假设我有一个序列：3（奇）、2（偶）、1（奇）、4（偶）。你试着手动交换一下，就会发现一个很有意思的事实：两个奇数（3 和 1）不管你怎么操作，它们在最终序列里的相对顺序永远是 3 在前、1 在后。因为要改变它们的相对顺序，必然存在某个时刻它们俩直接相邻并被交换，但两个奇数相邻时和是偶数，操作不合法。所以奇数的相对顺序是锁死的。

同理，偶数之间的相对顺序也是锁死的。这就是这个操作的本质约束：可以自由穿插，但同类之间的先后顺序不能变。

那可以自由到什么程度呢？其实你可以在任意一个奇数后面插入任意多个偶数，也可以把偶数移动到某些奇数前面。更准确地说，奇数可以作为一个“固定骨架”，偶数可以在它们之间任意穿梭。这就把一个看似无序的交换问题，变成了一个非常规整的重排问题。

1.3 从操作规则到问题的真正面目

搞清楚了操作的边界，题目就变得很清楚：允许我们自由调整奇偶之间的相对位置，但奇数和奇数内部、偶数和偶数内部的相对顺序不能动。

那问题问的通常是“能得到的字典序最小的序列”或者“某个特定位置的元素是谁”。这类问题的通用解法是：把原序列按奇偶拆成两条链——奇数链保持原顺序，偶数链保持原顺序——然后在合并的时候按某种贪心策略决定从哪条链取下一个元素。

如果你遇到的题目问的是字典序最小，那合并策略就是经典的归并式贪心：每次比较奇数链当前元素和偶数链当前元素，取数值较小的那个放到结果序列里。这个策略能成立，是因为两条链内部的相对顺序已经不能再变了，唯一能自由决定的，就是每一步到底取哪条链的下一个。

到这里，题目的“骨架”就已经掌握了。接下来要解决的就是三个问题：第一，贪心取数的正确性怎么证明；第二，怎么高效实现归并；第三，题目会不会有其他变形，比如交换次数限制、求某个位置的最终值、或者问有多少种可能结果。

2. 核心性质证明与边界条件

2.1 为什么同类相对顺序不可变——严格证明

很多题解对这条性质一笔带过，但我觉得值得展开说说，因为理解透了对做扩展题有很大帮助。假设序列里有两个奇数 a 和 b，a 在 b 的左边。我们要证明：无论执行多少次合法操作，a 始终在 b 的左边。

用反证法。假设存在一个操作序列，使得某个时刻 b 跑到了 a 的左边。那么在这个操作序列中，一定有某一次操作是 b 和某个元素交换，使得 b 从 a 的右侧跨到了 a 的左侧。考虑 b 和 a 之间的所有元素。在 b 跨越 a 的前一刻，b 必然和 a 相邻，并且它们进行了交换。这要求 b 和 a 的奇偶性不同。但 a 和 b 都是奇数，奇偶性相同，矛盾。因此假设不成立。

同理可证偶数之间的相对顺序也不可变。这个证明虽然简单，但它的意义在于：它告诉我们，这个问题的状态空间并不是所有排列，而是一个结构化的子集。正是因为有这种结构化约束，才能用归并贪心解决问题。

2.2 奇偶链之间可以任意穿插

同类相对顺序不变，那异类之间能穿插到什么程度？这里需要构造性证明。比如我有奇数链 [1, 5] 和偶数链 [2, 4]，我可以先把 2 通过一系列交换挪到 1 的前面吗？

实际上可以。想象冒泡排序里的交换：一个偶数可以在相邻的奇数之间“游走”，因为偶数和一个奇数相邻时永远满足交换条件。你只需要把它一步步往左或往右交换过去就行了。交换过程中，它可能会越过多个奇数，但这不改变任何奇数的相对顺序，也不改变其他偶数的相对顺序。

所以，最终可达的序列正是“奇数链保持原序、偶数链保持原序”的任意交错合并结果。这个结论非常关键——它意味着解法可以转化为一个很纯粹的组合问题，而不是一个搜索或 DP 问题。

2.3 字典序最小序列的贪心策略证明

如果题目要求字典序最小，那我们的直觉是每一步取两条链当前元素中较小的那个。这个直觉完全正确，但需要证明为什么局部最优就是全局最优。

假设当前奇数链头元素是 o，偶数链头元素是 e，且 o < e。如果我们在这一步取了 e，那么结果序列的下一位就是 e，而 o 还在链里。但如果取 o，结果序列的下一位是 o。因为字典序比较的就是第一位不同的大小，o < e 意味着第一位取 o 的序列字典序更小。无论后面怎么接，都不可能弥补第一位上的劣势。所以每一步取较小值，就是字典序意义上的最优选择。

这个证明适用于“当前链头的最小值就是全局剩余元素的最小值”的情况。但如果奇数链头和偶数链头并不是剩余所有元素中最小的怎么办？比如奇数链头是 99，偶数链头是 100，但奇数链第二个元素是 1——这不可能，因为奇数链保持原序，链头是奇数链里最小的吗？不是，链头是奇数链中原本最靠前的，但不一定数值最小。这就要小心了。

举个反例：奇数链是 [99, 1]，偶数链是 [50]。按“每次取两条链头较小的”策略，第一步比较 99 和 50，取 50；第二步比较 99 和 空，取 99；最后取 1。结果是 [50, 99, 1]。但如果我们第一步取 99（虽然是更大的数），得到 [99, 1, 50] 或 [99, 50, 1]——要比较 99 和 1，99 更大，所以 [99, 1, 50] 字典序更大；再看 [50, 99, 1] 和 [99, 1, 50]，第一位 50 < 99，所以 [50, 99, 1] 还是更小。看起来贪心还是对的。

但这里有个更隐蔽的问题：待比较的两个链头，真的是全局剩余元素中可能放在当前位置的最优人选吗？答案是：在“每次只能取两条链之一的下一个元素”的约束下，当前备选集合就只有这两个元素。因为两条链内部顺序不可变，你没有第三条路可选。所以上述贪心证明严格成立。理解了这一点，代码实现起来就很顺了。

2.4 需要警惕的序列边界情况

实战中容易出错的往往不是算法本身，而是边界情况的处理。

第一种情况是奇数链或偶数链为空。如果原序列全是奇数，那一条偶数链是空的，此时没有任何合法交换可以做，因为任意两个相邻元素都是奇数，和是偶数，不满足交换条件。答案就是原序列本身。这种情况在代码里容易导致数组越界或者比较逻辑出错。我建议在拆链之前就先判断：如果原序列里奇数个数为 0 或偶数个数为 0，直接输出原序列。

第二种情况是数值相同时怎么办。如果奇数链头和偶数链头数值相等，取哪个？从字典序角度来说，这一步没区别。但要注意后续影响：比如“奇数链当前位置还有一个更大的元素，而偶数链只剩一个元素”，那你选不同的链可能改变后续排列的可达性。虽然这种情况下取任意一个，第一位相同，但第二位可能不同。需要继续比较后续的链头来决定，不能随便选。稳妥的做法是：如果两个链头相等，就递归比较从两条链各取一个后的序列，但这会让实现变复杂。大多数题目在这类情况下，因为链内顺序固定，后续元素其实也被锁定了，所以选哪个最终字典序一样。为了保险，可以单独写一个比较函数：模拟取其中一条链之后，再比较两个结果的字典序大小。如果数据规模不大，这种方法最简单可靠。

3. 实现方案与复杂度分析

3.1 最直接的归并实现

弄清楚了算法思想，实现其实很机械。我们可以照搬归并排序的代码骨架，只不过合并的“两条链”不是按照数组下标切割的，而是按照奇偶性拆出来的两个独立数组。

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); vector<int> odd, even; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] % 2) odd.push_back(a[i]); else even.push_back(a[i]); } if (odd.empty() || even.empty()) { for (int i = 0; i < n; i++) { cout << a[i] << (i == n - 1 ? '\n' : ' '); } return 0; } vector<int> res; int i = 0, j = 0; while (i < odd.size() && j < even.size()) { if (odd[i] < even[j]) { res.push_back(odd[i++]); } else if (odd[i] > even[j]) { res.push_back(even[j++]); } else { // 相等时，模拟比较取哪条链更优 int ti = i + 1, tj = j + 1; while (ti < odd.size() && tj < even.size() && odd[ti] == even[tj]) { ti++; tj++; } if (tj == even.size() || (ti < odd.size() && odd[ti] < even[tj])) { res.push_back(odd[i++]); } else { res.push_back(even[j++]); } } } while (i < odd.size()) res.push_back(odd[i++]); while (j < even.size()) res.push_back(even[j++]); for (int i = 0; i < n; i++) { cout << res[i] << (i == n - 1 ? '\n' : ' '); } return 0; }

这段代码处理了链为空、相等元素这两个关键边界。相等时往后扫描的做法，本质上是在手动比较“接下来两个序列谁的字典序更小”。

3.2 时间复杂度与空间复杂度分析

拆链的过程遍历一次原数组，是 O(n)。归并过程每条链的每个元素恰好被取走一次，也是 O(n)。所以总时间复杂度是 O(n)。空间上，两个辅助数组和结果数组各存 n 个元素，是 O(n)。

这个复杂度意味着即使数据规模到几十万也能轻松跑过，内存占用也不大。相比某些用线段树维护逆序对的方案（那种通常是 O(n log n)），这个解法要简单不少。所以如果真的没有额外的操作次数限制，线性解法就是最优的。

3.3 如果题目有交换次数限制怎么办

有些变形题会加一个条件：最多允许 K 次交换，问最后能得到什么序列。这时问题就从贪心重排变成了一个带约束的问题，不能直接用上面的归并解法。

一种常见的处理思路是：把“交换”理解为“把一个偶数移动到某个位置需要消耗几步”。但这里有个坑——一个偶数越过几个奇数，需要几次交换？准确地说，越过 t 个奇数需要 t 次相邻交换，但这 t 次交换中，可能同时改变了偶数与其他偶数的相对位置。如果要保持偶数之间相对顺序不变，移动一个偶数越过的必须是全部奇数（或跟目标位置之间的奇数）。

对于带 K 限制的版本，一般不能再用简单的贪心，而要考虑搜索或 DP。比如可以枚举前 K 个操作的影响范围，或者按位置逐个决定最终序列的每位应该放奇数链头还是偶数链头，但要结合剩余操作次数来判断可行性。这已经超出基础题解的范围，但理解基础版本后，至少知道往哪个方向去思考。

3.4 一个基于两个队列的替代写法

如果觉得双指针加数组麻烦，也可以直接用两个队列来实现。把奇数按原顺序入奇队列，偶数按原顺序入偶队列，然后每次比较队头、出队并入结果序列。代码逻辑完全一样，只是不需要手动维护下标。

但我个人更推荐双指针数组写法。因为调试时可以直接看到两个下标的位置和对应值，比队列更直观。而且如果要支持“取回”或“预读”等操作，数组写法灵活得多。队列适合思路已经很熟、确认代码不会出错的场景。

4. 常见错误与避坑经验

4.1 忽略空链导致的行为异常

这是最容易被忽略的错误。很多人在实现时默认两条链都非空，直接写 while 循环，等其中一条链取空了再用另一个循环把剩余的补上。逻辑上没问题，但如果一开始就有一条链是空的，就会出现一些奇怪的行为——比如链头访问越界，或者直接跳进补剩循环，结果输出的序列跟原序列不一致。

比如原序列是 [2, 2, 4]，全是偶数。拆链后偶队列是 [2, 2, 4]，奇队列是空。如果代码在 while (i < odd.size() && j < even.size()) 里先访问 odd[i]，这已经越界了，在 C++ 里是未定义行为，可能直接 RE。所以第一个要判断的就是空链情况。

4.2 自认为“相等时随便取”导致的隐性错误

我在 2.4 节提过相等元素的处理。很多初学者会认为，两个数相等，取哪一个输出结果都一样，于是直接用if (odd[i] <= even[j])取奇数链。这在前半段可能没错，但后续可能会错。

举个具体的例子。奇数链是 [3, 1]，偶数链是 [3, 4]。第一次比较两个链头都是 3。如果贪心取奇数链，结果是 [3, 1, 3, 4]；如果取偶数链，结果是 [3, 3, 1, 4]。比较两个结果：第一位都是 3，第二位 1 < 3，所以取奇数链之后的结果字典序更小。你看，第一次相等时选哪一个，确实会影响后面的结果。所以相等时必须深度比较后续元素，不能简单随便取一个。

这也是这类题最刁钻的地方——看起来不影响首位的选择，实际影响第二位、第三位。我的习惯是：只要链头相等，就写一个专门的小函数模拟取两种选择后的序列，直接比较字典序。因为序列长度可能很大，完整模拟是 O(n) 的，如果每次相等都比较一次，整体复杂度会退化成 O(n^2)。更高效的做法是像我在 3.1 里写的那样，只往后扫描到第一个不相等的元素，根据那个更小值所在的链决定取哪边。这本质上是把比较过程剪枝了。

4.3 用 sort 拆链导致结果错误

另一类常见错误是把问题理解成了“把所有奇数排序、所有偶数排序”。如果这样做，得到的序列确实可能满足“奇偶穿插”的形式，但它违背了同类相对顺序不可变的约束。

比如原序列 [5, 1, 4, 2]，奇数链按原序是 [5, 1]，但如果用 sort 会变成 [1, 5]。原本 5 必须在 1 前面，可排序后 1 跑到 5 前面去了，这个操作在原始规则下根本不可达。所以得到的结果虽然可能也是一个“合法序列”，但它并不是从原序列经过合法操作能够到达的状态。这个错误很容易被样例骗过去——因为很多样例恰好选的数据里，奇数链本来就是升序或降序。

4.4 数据过大时用递归模拟交换导致的超时

有相当一部分人会选择直接模拟整个交换过程，比如每次寻找相邻的奇偶元素并交换，直到不能交换为止。这种思路在小数据下能过，但数据量到十万级、百万级时，交换次数可能接近 O(n^2)，一定会超时。

我们的 O(n) 解法完全不模拟任何交换。因为我们已经证明，最终结果只取决于奇数链和偶数链的内部顺序，以及每一步的合并选择。模拟是手段，不是目的。记住这个原则：遇到这类“可交换但是有条件”的题，先分析不变量，再决定怎么重排。

4.5 多组测试数据时没有清空数组

AtCoder 的题目经常有多组测试数据（T 组）。如果使用全局数组，每次处理完一组必须清空或重置长度标记。C++ 里最常见的坑是：每次循环里直接 push_back 到同一个 vector，而忘记在开始前 clear。结果上一组数据残留的数据跟当前组混在一起，导致拆链错误或输出长度错误。建议每组数据都新建局部 vector，或者在循环体开头统一 clear。

5. 实测案例演示与过程记录

5.1 案例一：普通混合序列

输入序列：3 8 1 6 5 2 4 7

拆链：

• 奇数链：[3, 1, 5, 7]
• 偶数链：[8, 6, 2, 4]

按贪心归并：

• 比较 3 和 8，取 3
• 比较 1 和 8，取 1
• 比较 5 和 8，取 5
• 比较 7 和 8，取 7
• 奇数链取完，按顺序补偶数链 [8, 6, 2, 4]

所以最终序列：3 1 5 7 8 6 2 4

可以验证一下可达性：奇数链相对顺序是 3→1→5→7，最终序列中它们确实保持这个相对顺序；偶数链相对顺序是 8→6→2→4，最终序列中的偶数部分也保持这个顺序。每条链内部顺序没乱，说明合法。

5.2 案例二：含有相等链头，验证 4.2 的坑

输入序列：3 1 3 4（奇数链 [3, 1]，偶数链 [3, 4]）

如果使用朴素策略“小于取奇、大于取偶、等于随便取奇数链”，得到：

• 取 3（奇数链头）
• 奇数链剩下 [1]，偶数链 [3, 4]
• 比较 1 和 3，取 1
• 偶数链 [3, 4] 全部补上

结果是3 1 3 4。

如果取偶数链：

• 取 3（偶数链头）
• 奇数链 [3, 1]，偶数链 [4]
• 比较 3 和 4，取 3（奇数链）
• 比较 1 和 4，取 1
• 补 4

结果是3 3 1 4。

很明显3 1 3 4字典序更小。所以相等时“随便取”是错的。代码里需要像 3.1 那样做链头相等时的后续比较。

5.3 案例三：全奇数序列的特殊判断

输入序列：5 7 9。全奇数，奇数链 [5, 7, 9]，偶数链为空。没有任何合法操作，答案就是原序列5 7 9。如果不做空链判断，常见的错误写法会在访问 even[j] 时因为 j 越界而崩溃，甚至在某些编译器上因为数组越界但恰好没崩溃而输出错误结果。

5.4 案例四：交错排列的复杂情况

输入序列：2 5 4 7 6 9 8

奇偶链分配：

• 奇数链：[5, 7, 9]
• 偶数链：[2, 4, 6, 8]

贪心归并过程：

• 比较 5 和 2，取 2
• 比较 5 和 4，取 4
• 比较 5 和 6，取 5
• 比较 7 和 6，取 6
• 比较 7 和 8，取 7
• 比较 9 和 8，取 8
• 补 9

最终序列：2 4 5 6 7 8 9

可以看到，这个结果把所有元素按升序排好了。但这只是一个巧合——因为原始序列恰好已经具备了“奇数链和偶数链各自有序”的特征。并不是说这个算法总是输出全局升序，而是这个样例里数字刚好这么凑巧。别把这个案例当成结论。

5.5 案例五：逆序性较强的序列

输入序列：9 8 7 6 5 4 3 2 1

奇数链：[9, 7, 5, 3, 1] 偶数链：[8, 6, 4, 2]

贪心过程：

• 比较 9 和 8，取 8
• 比较 9 和 6，取 6
• 比较 9 和 4，取 4
• 比较 9 和 2，取 2
• 奇数链剩余 [9, 7, 5, 3, 1] 全部补上

最终序列：8 6 4 2 9 7 5 3 1

可以看到偶数全部被挪到了前面，奇数保持原来的降序。这其实是最优的字典序结果，因为偶数链的最小值是 2，而奇数链的最小值是 1，但 1 前面还有 9、7、5、3 这几个“障碍”，要取到 1 必须先取 9 或更大的值，那不如先把偶数链全部取完。这是一个非常好的例子，能帮你理解为什么贪心是基于“链头”，而不是基于“全局最小值”。

6. 题目变形与扩展思考

6.1 换成“乘积为偶数”或其他条件

原题用的是“和为奇数”，但这类题可以有很多变体。比如把条件改成“乘积为偶数”，效果等价于至少有一个是偶数，那任意两个数之间只要有一个偶数就能交换。再比如改成“和为偶数”，那同类之间反而可以交换，异类不能，结论会完全反过来。拿到变形题，第一件事永远是分析交换条件对应到奇偶性分类后的关系，然后重新判断哪些相对顺序是不变量。

6.2 如果要求输出所有可能序列

有些进阶题不问你字典序最小，而是问有多少种不同的可达序列。这时问题就变成了：给定两条保持原序的链，问有多少种交错合并的方式。这是经典的组合计数问题，答案是 C(|奇数链| + |偶数链|, |奇数链|)，即从总位置里选奇数链位置的方法数。如果要求取模，再套一个组合数预处理模板就行。

6.3 扩展到三维、多维属性

如果每个元素有两个属性（比如奇偶性和正负性），交换条件变成“两个属性同时满足某种关系才可交换”，那么可交换性就变成了一种图论结构。此时问题就不是简单的两条链合并，而可能是多个连通分量内的重排问题。这种情况下，通常要先把元素按某种等价关系分组，再在组内做贪心。这种变形题在竞赛中出现过多次，本质是把“可交换”关系转化成“连通块”，再在每个连通块内独立求解。

6.4 逆序对视角的另一种理解

另一个值得提的切入角度是逆序对。在原题条件下，可交换操作等价于“消除一个逆序对，但仅限于奇偶性不同的相邻逆序对”。同类之间的逆序对无法消除。所以最后得到的序列中，同类元素之间的逆序关系保持不变。这个视角在做“确定能否排序成升序”类的题目时特别有用——如果题目问能否把序列变成严格递增，你需要检查的其实是：剔除所有偶数后，奇数序列是否递增；剔除所有奇数后，偶数序列是否递增。只要这两条链各自递增，就一定可以通过操作得到一个完全有序的序列，因为两条链之间可以任意穿插，最终一定能把全局排成升序。

6.5 交换次数计数问题

还有一类变形问“从初始状态到目标状态最少需要多少次交换”。在相邻交换模型下，最少次数等于目标序列相对于原序列的逆序对数（更准确地说，是目标序列中每一对元素在原序列中的相对顺序被改变的对数）。这个量不好直接算，但可以通过树状数组在 O(n log n) 内求出。通常只有在题目限定目标序列时才会这么做，如果目标也是可变的，那就又是一道优化题了。

7. 最后的实操建议

做这类题，我个人的经验有三条。第一条，拿到题先花五分钟手推几个小样例，尤其要构造那种含有相等元素、全奇数、全偶数的极端用例，不要在正确性没把握时直接写代码。第二条，实现时把“空链”和“链头相等”这两个分支单独处理，宁多写几行，不要省事合并逻辑。第三条，如果时间允许，用一个小暴力程序做对拍：随机生成短序列，用 BFS 模拟所有可能的交换结果，再和贪心结果比较。对拍个几百组，基本能确认代码正确。

这道题最大的价值不在于它的解法本身，而在于它反复提醒我们：当一个系统存在约束时，先找“不变量”，再在不变量的框架内做贪心或搜索。同类相对顺序不变，就是这道题的不变量。把握住不变量，整个问题就从混沌变得清晰。希望这篇题解能让你少走一些弯路，下次遇到同类问题时，能更快地抓住要害。