小欧的排列交换

OPPO 笔试真题 · 2023 秋招 · 移动端岗

判题请到牛客原题提交。

题目描述

小欧拿到了一个长度为 $n$ 的排列。她每次操作可以交换任意两个数。她希望在不超过 $n-1$ 次操作后，使得不存在两个相邻的数都是奇数，也不存在两个相邻的数都是偶数。你能帮帮她吗？

所谓排列，即 1 到 n 组成的数组，每个数仅出现 1 次。

输入格式

第一行输入一个正整数 $n$，代表排列的长度。

第二行输入 $n$ 个正整数 $a_i$，代表小欧拿到的排列。

$1\leq n \leq 10^5$

输出格式

第一行输出一个整数 $k$，代表交换的次数。

接下来的 $k$ 行，每行输出两个正整数 $a_i$ 和 $a_j$，代表交换这两个数。

有多种方案时，输出任意合法方案即可。

示例

示例 1

输入：

3
3 1 2

输出：

1
1 2

---

解题思路

第一步：理解问题本质

要求「不存在两个相邻的数都是奇数，也不存在两个相邻的数都是偶数」——
换句话说，奇偶性必须严格交替：奇、偶、奇、偶……

我们其实不关心每个位置具体放哪个数，只关心它放的是奇数还是偶数。
而 $1$ 到 $n$ 中奇数有 $\lceil n/2\rceil$ 个、偶数有 $\lfloor n/2\rfloor$ 个，
两者要么相等（$n$ 为偶数），要么奇数多一个（$n$ 为奇数），
所以交替排列一定存在。

第二步：奇偶骨架是唯一确定的

以 $n=5$ 为例，奇数有 $1,3,5$ 三个、偶数有 $2,4$ 两个。
交替排列只能长这样：奇、偶、奇、偶、奇 —— 奇数必须占第 $1,3,5$ 位，
偶数必须占第 $2,4$ 位。

$n$ 为偶数时（比如 $n=4$），奇偶各两个，两种骨架都可行
（奇偶奇偶，或偶奇偶奇），任选一种即可，对做法没有影响。

下面统一采用「奇数放奇数位、偶数放偶数位」这一种骨架。

第三步：哪些位置是「错」的

把每个位置分成两类：

• A 类：位置编号是奇数（该放奇数），但当前放的是偶数；
• B 类：位置编号是偶数（该放偶数），但当前放的是奇数。

因为数组是 $1$ 到 $n$ 的排列，奇数总数和偶数总数都对得上骨架，
所以 A 类和 B 类的个数一定相等。

第四步：两两配对交换

从 A 类里取一个位置、B 类里取一个位置，交换它们上面的数：
A 类位置拿到了奇数（修好），B 类位置拿到了偶数（也修好）。
一次交换修好两个位置，总共只需要「A 类的个数」次交换。

A 类的个数最多是 $\lfloor n/2\rfloor$，而题目允许 $n-1$ 次交换。
$n\ge 2$ 时 $\lfloor n/2\rfloor\le n-1$ 恒成立（$n=2$ 时两边都是 1），
$n=1$ 时根本不需要交换，所以次数约束天然满足。

第五步：输出的是数值，不是下标

注意题面：「每行输出两个正整数 $a_i$ 和 $a_j$，代表交换这两个数」——
输出的是数值。因为数组是排列、每个数只出现一次，按值交换没有歧义。
样例里 1 2 交换的就是值为 1 和值为 2 的两个数。

---

完整代码实现

import sys


def solve():
    """把「该放奇数却放了偶数」和「该放偶数却放了奇数」的位置两两交换"""
    data = sys.stdin.buffer.read().split()
    if not data:
        return
    n = int(data[0])
    a = [int(t) for t in data[1:1 + n]]

    need_odd = []    # 位置（1 起）需要奇数，但当前放的是偶数
    need_even = []   # 位置（1 起）需要偶数，但当前放的是奇数
    for idx in range(1, n + 1):
        want_odd = idx % 2 == 1
        is_odd = a[idx - 1] % 2 == 1
        if want_odd and not is_odd:
            need_odd.append(idx)
        elif not want_odd and is_odd:
            need_even.append(idx)

    swaps = []
    for p, q in zip(need_odd, need_even):
        # 交换这两个位置上的「数值」，输出时用的是数值本身
        swaps.append((a[q - 1], a[p - 1]))

    out = [str(len(swaps))]
    out += [f"{x} {y}" for x, y in swaps]
    sys.stdout.write("\n".join(out) + "\n")


if __name__ == "__main__":
    solve()

---

示例推演

样例：$n=3$，排列是 3 1 2。

第一步：确定骨架

$n=3$ 时奇数有 $1,3$ 两个，所以奇数必须占第 1、3 位，第 2 位放偶数。

第二步：逐位对照

位置	当前值	奇偶	该位置应该放	是否错位	归类
1	3	奇	奇	否	—
2	1	奇	偶	是	B 类（该放偶，放了奇）
3	2	偶	奇	是	A 类（该放奇，放了偶）

第三步：配对交换

A 类只有一个位置 3，B 类只有一个位置 2，交换它们：

交换的数值	交换后数组
1 和 2	3 2 1

第 2 位现在是 2（偶），第 3 位是 1（奇），奇偶性变成 奇、偶、奇，满足要求。

第四步：输出

交换次数 1，然后是 1 2：

1
1 2

与样例输出完全一致。如果把 1 2 理解成「下标 1 和下标 2」，
交换的是 3 和 1，得到 1 3 2，奇偶性是 奇、奇、偶，反而更糟 ——
这正是本题最容易误读的地方。

---

复杂度分析

解法	时间复杂度	空间复杂度	说明
逐位模拟交换（每次修好一个位置）	$O(n^2)$	$O(n)$	每次找目标值都要扫一遍，最坏超时
错位位置两两配对	$O(n)$	$O(n)$	推荐，一遍扫描 + 一遍配对

---

易错点总结

1. 输出的是数值而不是下标

题面样例已经说明了：1 2 交换的是值为 1 的数和值为 2 的数。
输出下标会得到完全不同的结果，而且判题会直接判错。

2. 交换次数要满足 $k\le n-1$

配对法最多交换 $\lfloor n/2\rfloor$ 次，一定不超过 $n-1$。
如果改用「从左到右逐个位置找到该放的值再交换」的写法，每次交换至少
让一个位置归位，所以次数也不超过 $n-1$，同样安全。
真正会出问题的是「每次只修好一个位置却把位置重复算一遍」的写法，
那样可能多换很多次。

3. $n=1$ 要输出 0

此时不需要任何交换，第一行是 0，后面没有别的行。
不要输出多余的空白行。

4. 骨架不能随便选

$n$ 为奇数时必须「奇数占奇数位」，因为奇数个数比偶数多一个。
如果为了省事把所有位置都按「偶数位放偶数」的相反骨架处理，
$n$ 为奇数时会无解。

5. 别忘了「排列」意味着每个数只出现一次

这是「按值交换无歧义」的前提。如果数组里允许重复值，
题目的输出格式就得改成下标了。

---

扩展思考

• 为什么配对法是最优的？每次交换最多修好两个位置，而每个错位位置
  都必须参与至少一次交换，所以交换次数至少是「错位位置数的一半」，
  配对法恰好达到这个下界。
• 若要求输出字典序最小的方案，就要在「修好位置」的前提下选择最小的配对，
  做法会变成贪心 + 有序集合。
• 若操作改成「只能交换相邻两个数」，最少次数就等于把每个奇数（或偶数）
  挪到目标位置所需的总位移，即逆序对相关的计算。
• 这类题的核心思路是：把「数值」抽象成「类别」（奇/偶），
  问题就从「重排整个排列」降级成「调整两类元素的位置」。

---

相关题目

• 小欧的排列计算
• 小欧的字符交换