题解 | #小红的排列构造①#

题目链接

小红的排列构造①

题目描述

小红希望你构造一个长度为 $n$ 的排列 $p$ ，使得对所有 $i \in [1, n]$ ，都有 $p_i + i$ 不是质数。

长度为 $n$ 的排列是由 $1, 2, \dots, n$ 这 $n$ 个正整数按任意顺序组成的数组，其中每个整数恰好出现一次。

解题思路

这是一个构造性问题。我们需要找到一个排列 $p$ ，使得所有的 $p_i + i$ 都是合数。

一个关键的突破口是考虑 $p_i+i$ 的奇偶性。如果一个数是大于 $2$ 的偶数，那么它一定是合数。

两个奇数之和是偶数。
两个偶数之和是偶数。

这启发我们可以将排列中的数和它们的下标按照奇偶性进行配对。也就是说：

如果下标 $i$ 是奇数，我们就让 $p_i$ 也为奇数。
如果下标 $i$ 是偶数，我们就让 $p_i$ 也为偶数。

这样一来， $p_i+i$ 的结果就总是偶数。现在，我们只需要处理一种特殊情况： $p_i + i = 2$ 。这种情况会发生当且仅当 $i=1$ 且 $p_1=1$ ，因为 $p_i$ 和 $i$ 都是正整数。如果 $p_1+1=2$ ，而 $2$ 是质数，那么这个构造就失败了。

所以，我们的构造目标是：

奇数下标 $i$ 对应奇数值 $p_i$ 。
偶数下标 $i$ 对应偶数值 $p_i$ 。
必须避免 $p_1=1$ 。

我们可以采用一个简单的构造方法：将所有偶数放在排列的前面，然后将所有奇数放在排列的后面。

具体来说，排列 $p$ 构造为： $[2, 4, 6, \dots, \text{所有偶数}, 1, 3, 5, \dots, \text{所有奇数}]$ 。

我们来验证这个构造是否满足条件：

这是一个 $1$ 到 $n$ 的排列吗？是的，它包含了 $1$ 到 $n$ 的所有整数，每个恰好出现一次。
对于每个 $i$ ， $p_i+i$ 是合数吗？
- 当 $n < 3$ 时：
  - $n=1$ ：排列为 $[1]$ 。 $p_1+1=2$ (质数)，不满足。
  - $n=2$ ：排列为 $[2, 1]$ 。 $p_1+1=3$ (质数)，不满足。
- 当 $n \ge 3$ 时：
  - 对于偶数部分 $p_i = 2 \cdot i$ （其中 $i=1, \dots, \lfloor \frac{n}{2} \rfloor$ ）：
    - 此时 $p_i$ 是偶数，下标 $i$ 可能是奇数或偶数。
    - $p_1=2, p_2=4, \dots$
    - $p_1+1 = 2+1=3$ (质数)，这个构造方法在 $n \ge 2$ 时行不通。

看来简单的拼接不行，我们需要一个更精细的构造。回到奇偶配对的思路上，我们只需要保证 $p_1 \neq 1$ 即可。一个简单的实现是，在各自的奇偶数集合内部进行循环移位。

偶数部分： $p_2=4, p_4=6, \dots, p_{last\_even}=2$ 。
奇数部分： $p_1=3, p_3=5, \dots, p_{last\_odd}=1$ 。

这样构造，对于任意 $i \in [1, n]$ ， $p_i$ 和 $i$ 的奇偶性都相同，所以 $p_i+i$ 是偶数。同时，因为 $n \ge 3$ 时奇数至少有 $1, 3$ 两个，所以 $p_1$ 会被赋值为 $3$ ，从而 $p_1 \ne 1$ ，这就保证了 $p_1+1 \ne 2$ 。

总结一下最终的构造方案：

当 $n < 3$ 时，不存在满足条件的排列，输出 -1。
当 $n \ge 3$ 时：
- 将 $2, 4, \dots, n$ （或 $n-1$ ）中的偶数依次填入 $p_2, p_4, \dots$ 。具体来说，就是 $p_i = i+1$ 。
- 然后将 $1, 3, \dots, n$ （或 $n-1$ ）中的奇数依次填入 $p_1, p_3, \dots$ 。具体来说，也是 $p_i = i+1$ 。
- 这种构造等价于 $p_i = i+1$ for $i=1 \dots n-1$ ， $p_n=1$ 。
- 让我们验证一下这个更简单的构造： $p = [2, 3, 4, \dots, n, 1]$
  - For $i \in [1, n-1]$ : $p_i+i = (i+1)+i = 2i+1$ 。我们需要保证 $2i+1$ 不是质数。例如当 $i=2$ , $2i+1=5$ 是质数。所以这个简单构造也不行。

让我们回到最初最可靠的 奇偶数内部循环移位 构造方案。

对于所有偶数下标 $i \in [2, n]$ ，令 $p_i$ 为 $i$ 的下一个偶数。最后一个偶数下标对应的 $p$ 值为第一个偶数 $2$ 。
对于所有奇数下标 $i \in [1, n]$ ，令 $p_i$ 为 $i$ 的下一个奇数。最后一个奇数下标对应的 $p$ 值为第一个奇数 $1$ 。

这个方案可以保证 $p_i$ 与 $i$ 奇偶性相同，且当 $n \ge 3$ 时 $p_1=3 \ne 1$ ，因此 $p_i+i$ 总是大于 $2$ 的偶数，即合数。

代码

c++
java
python

#include <iostream>
#include <vector>
#include <numeric>

using namespace std;

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

    if (n < 3) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> p(n + 1);
    
    // 构造偶数部分的映射
    for (int i = 2; i <= n; i += 2) {
        if (i + 2 <= n) {
            p[i] = i + 2;
        }
    }
    int last_even = (n % 2 == 0) ? n : n - 1;
    p[last_even] = 2;

    // 构造奇数部分的映射
    for (int i = 1; i <= n; i += 2) {
        if (i + 2 <= n) {
            p[i] = i + 2;
        }
    }
    int last_odd = (n % 2 != 0) ? n : n - 1;
    p[last_odd] = 1;
    
    for (int i = 1; i <= n; ++i) {
        cout << p[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        if (n < 3) {
            System.out.println(-1);
            return;
        }

        int[] p = new int[n + 1];
        
        // 构造偶数部分的映射
        for (int i = 2; i <= n; i += 2) {
            if (i + 2 <= n) {
                p[i] = i + 2;
            }
        }
        int lastEven = (n % 2 == 0) ? n : n - 1;
        p[lastEven] = 2;

        // 构造奇数部分的映射
        for (int i = 1; i <= n; i += 2) {
            if (i + 2 <= n) {
                p[i] = i + 2;
            }
        }
        int lastOdd = (n % 2 != 0) ? n : n - 1;
        p[lastOdd] = 1;

        for (int i = 1; i <= n; i++) {
            System.out.print(p[i] + (i == n ? "" : " "));
        }
        System.out.println();
    }
}

n = int(input())

if n < 3:
    print(-1)
else:
    p = [0] * (n + 1)
    
    # 构造偶数部分的映射
    i = 2
    while i <= n:
        if i + 2 <= n:
            p[i] = i + 2
        i += 2
    last_even = n if n % 2 == 0 else n - 1
    p[last_even] = 2
    
    # 构造奇数部分的映射
    i = 1
    while i <= n:
        if i + 2 <= n:
            p[i] = i + 2
        i += 2
    last_odd = n if n % 2 != 0 else n - 1
    p[last_odd] = 1
    
    result = []
    for i in range(1, n + 1):
        result.append(str(p[i]))
    print(" ".join(result))

算法及复杂度

算法：数学、构造
时间复杂度： $\mathcal{O}(n)$ ，需要遍历两次（奇数和偶数）来填充排列数组。
空间复杂度： $\mathcal{O}(n)$ ，需要一个长度为 $n$ 的数组来存储构造的排列。