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

题目链接

题目描述

给定一个正整数 $n$ ，要求构造一个长度为 $n$ 的排列 $p$ (即 $1$ 到 $n$ 这 $n$ 个数每个都出现一次)，使得对于所有的 $i$ ( $1 \le i \le n$ )， $p_i + i$ 的值都不是质数。如果不存在这样的排列，则输出 -1。

输入:

一个正整数 $n$ 。

输出:

一行 $n$ 个整数，表示构造的排列。如果不存在，则输出 -1。

解题思路

这是一个构造性问题。核心目标是让 $p_i + i$ 对所有 $i$ 都为合数。

一个有效的策略是让 $p_i + i$ 成为一个大于2的偶数，因为大于2的偶数都是合数。要使和为偶数，两个加数必须具有相同的奇偶性。因此，我们可以尝试构造一个排列 $p$ ，使得任意位置 $i$ 和该位置上的元素 $p_i$ 的奇偶性相同。

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

这样，问题被分解为两个独立的子问题：

对所有奇数位置，用所有奇数元素 $\{1, 3, 5, \dots\}$ 构成一个排列。
对所有偶数位置，用所有偶数元素 $\{2, 4, 6, \dots\}$ 构成一个排列。

一个简单的构造方法是对奇数集合和偶数集合分别进行循环移位。例如，对于奇数序列 $[1, 3, 5]$ ，我们可以构造排列 $1 \to 3, 3 \to 5, 5 \to 1$ 。这样可以保证 $p_i \neq i$ (只要集合中元素多于一个)。

现在需要考虑特殊情况：

当 $p_i + i$ 可能等于2时。这只在 $i=1$ 且 $p_1=1$ 时发生，因为 $p_i \ge 1, i \ge 1$ 。
$n=1$ : 排列为 $p=[1]$ 。 $p_1+1=2$ ，是质数。无解。
$n=2$ : 排列为 $[1, 2]$ 或 $[2, 1]$ 。
- 对于 $p=[1, 2]$ ， $p_1+1=2$ ，是质数。
- 对于 $p=[2, 1]$ ， $p_1+1=3$ ，是质数。
- 无解。

对于 $n \ge 3$ 的情况：

奇数集合至少包含 $\{1, 3\}$ 。
偶数集合至少包含 $\{2\}$ 。我们的同奇偶性策略是可行的。通过对奇数和偶数集合分别进行循环移位，可以保证 $p_1$ 被赋予 $3$ ，所以 $p_1+1 = 4$ ，不是质数2。对于所有其他 $i$ ， $p_i+i$ 也是大于2的偶数，因此是合数。

所以，最终的构造算法如下：

如果 $n=1$ 或 $n=2$ ，输出 -1。
如果 $n \ge 3$ ，将 $1$ 到 $n$ 的数字分为奇数组和偶数组。
通过对奇数组进行循环左移1位来确定所有奇数位置的排列值。
通过对偶数组进行循环左移1位来确定所有偶数位置的排列值。
组合并输出最终排列。

代码

c++
java
python

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

using namespace std;

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

    if (n == 1 || n == 2) {
        cout << -1 << endl;
        return 0;
    }

    vector<int> p(n + 1);
    vector<int> odds, evens;

    for (int i = 1; i <= n; ++i) {
        if (i % 2 != 0) {
            odds.push_back(i);
        } else {
            evens.push_back(i);
        }
    }

    // 对奇数进行循环移位排列
    for (size_t i = 0; i < odds.size(); ++i) {
        p[odds[i]] = odds[(i + 1) % odds.size()];
    }

    // 对偶数进行循环移位排列
    for (size_t i = 0; i < evens.size(); ++i) {
        p[evens[i]] = evens[(i + 1) % evens.size()];
    }

    for (int i = 1; i <= n; ++i) {
        cout << p[i] << (i == n ? "" : " ");
    }
    cout << endl;

    return 0;
}

import java.util.Scanner;
import java.util.ArrayList;
import java.util.List;

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

        if (n == 1 || n == 2) {
            System.out.println(-1);
            return;
        }

        int[] p = new int[n + 1];
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            if (i % 2 != 0) {
                odds.add(i);
            } else {
                evens.add(i);
            }
        }

        // 对奇数进行循环移位排列
        for (int i = 0; i < odds.size(); i++) {
            p[odds.get(i)] = odds.get((i + 1) % odds.size());
        }

        // 对偶数进行循环移位排列
        for (int i = 0; i < evens.size(); i++) {
            p[evens.get(i)] = evens.get((i + 1) % evens.size());
        }

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

n = int(input())

if n == 1 or n == 2:
    print(-1)
else:
    p = [0] * (n + 1)
    odds = []
    evens = []
    for i in range(1, n + 1):
        if i % 2 != 0:
            odds.append(i)
        else:
            evens.append(i)
    
    # 对奇数进行循环移位排列
    for i in range(len(odds)):
        p[odds[i]] = odds[(i + 1) % len(odds)]
        
    # 对偶数进行循环移位排列
    for i in range(len(evens)):
        p[evens[i]] = evens[(i + 1) % len(evens)]
        
    result = [str(p[i]) for i in range(1, n + 1)]
    print(" ".join(result))

算法及复杂度

算法：构造法、奇偶性匹配
时间复杂度： $\mathcal{O}(n)$ - 需要遍历 $1$ 到 $n$ 来分离奇偶数，然后再次遍历填充排列，总时间复杂度为线性。
空间复杂度： $\mathcal{O}(n)$ - 需要使用数组或列表来存储奇数、偶数以及最终的排列。