1. 题目理解与核心思路1.1 先别急着写代码把操作本质看懂这道题一上来给出的操作看起来很简单选两个相邻的元素如果它们的和是奇数就交换它们的位置。很多新手看到这里容易产生一个直觉——这不就是冒泡排序的变种吗直接模拟就行了。但如果你真的去模拟十有八九会在第 20 个测试点超时或者在某个隐蔽的边界情况上 WA 到怀疑人生。因为题目的关键根本不在“怎么模拟交换”而是在“这个操作到底能改变什么、不能改变什么”。那两个数的和是奇数意味着什么想想奇偶性的基本规则奇数加奇数等于偶数偶数加偶数等于偶数只有奇数加偶数或者反过来才等于奇数。所以这个操作的真正含义是——只有当两个相邻元素的奇偶性不同时才能交换它们。换句话说一个奇数和它相邻的偶数可以互换位置但两个奇数之间、两个偶数之间永远不可能通过这个操作直接交换。这个观察是整个题目的分水岭。后面所有结论都建立在它之上。你要是没想透这一点后面看官方题解的讨论区间、讨论逆序对都会觉得莫名其妙。1.2 这个限制条件藏着整个问题的解法有了“只有奇偶性不同的相邻元素才能交换”这个前提接下来的问题就是那我能通过一系列操作把序列变成什么样举个例子假设我有一个序列3奇、2偶、1奇、4偶。你试着手动交换一下就会发现一个很有意思的事实两个奇数3 和 1不管你怎么操作它们在最终序列里的相对顺序永远是 3 在前、1 在后。因为要改变它们的相对顺序必然存在某个时刻它们俩直接相邻并被交换但两个奇数相邻时和是偶数操作不合法。所以奇数的相对顺序是锁死的。同理偶数之间的相对顺序也是锁死的。这就是这个操作的本质约束可以自由穿插但同类之间的先后顺序不能变。那可以自由到什么程度呢其实你可以在任意一个奇数后面插入任意多个偶数也可以把偶数移动到某些奇数前面。更准确地说奇数可以作为一个“固定骨架”偶数可以在它们之间任意穿梭。这就把一个看似无序的交换问题变成了一个非常规整的重排问题。1.3 从操作规则到问题的真正面目搞清楚了操作的边界题目就变得很清楚允许我们自由调整奇偶之间的相对位置但奇数和奇数内部、偶数和偶数内部的相对顺序不能动。那问题问的通常是“能得到的字典序最小的序列”或者“某个特定位置的元素是谁”。这类问题的通用解法是把原序列按奇偶拆成两条链——奇数链保持原顺序偶数链保持原顺序——然后在合并的时候按某种贪心策略决定从哪条链取下一个元素。如果你遇到的题目问的是字典序最小那合并策略就是经典的归并式贪心每次比较奇数链当前元素和偶数链当前元素取数值较小的那个放到结果序列里。这个策略能成立是因为两条链内部的相对顺序已经不能再变了唯一能自由决定的就是每一步到底取哪条链的下一个。到这里题目的“骨架”就已经掌握了。接下来要解决的就是三个问题第一贪心取数的正确性怎么证明第二怎么高效实现归并第三题目会不会有其他变形比如交换次数限制、求某个位置的最终值、或者问有多少种可能结果。2. 核心性质证明与边界条件2.1 为什么同类相对顺序不可变——严格证明很多题解对这条性质一笔带过但我觉得值得展开说说因为理解透了对做扩展题有很大帮助。假设序列里有两个奇数 a 和 ba 在 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 和 199 更大所以 [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; vectorint a(n); vectorint 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; } vectorint 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 模拟所有可能的交换结果再和贪心结果比较。对拍个几百组基本能确认代码正确。这道题最大的价值不在于它的解法本身而在于它反复提醒我们当一个系统存在约束时先找“不变量”再在不变量的框架内做贪心或搜索。同类相对顺序不变就是这道题的不变量。把握住不变量整个问题就从混沌变得清晰。希望这篇题解能让你少走一些弯路下次遇到同类问题时能更快地抓住要害。