小红的排列构造①

思路

这道题要求构造一个长度为 的排列，使得每个位置 都满足 不是质数。

先看小情况：

  • ：排列只有 ， 是质数，无解。
  • ： 给出 ， 给出 ，怎么放都有质数，无解。

那 呢？有一个非常巧妙的构造：把前三个位置放 ，后面的位置 （）直接放 本身。

为什么这样是对的？

  • 位置 1 放 3：，合数 ✓
  • 位置 2 放 2：，合数 ✓
  • 位置 3 放 1：，合数 ✓
  • 位置 （）放 ：，是大于 2 的偶数，一定是合数 ✓

前三个位置的和全是 4，后面位置的和是 ，都是偶数且 ，不可能是质数。完美！

这个构造的关键洞察是：恒等排列 几乎就是答案，唯一的问题在位置 1（ 是质数）。而把前三个数翻转一下，所有的和都变成 4，问题就解决了。

代码

#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    if(n<=2){
        printf("-1\n");
        return 0;
    }
    printf("3 2 1");
    for(int i=4;i<=n;i++) printf(" %d",i);
    printf("\n");
    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 <= 2) {
            System.out.println(-1);
            return;
        }
        StringBuilder sb = new StringBuilder();
        sb.append("3 2 1");
        for (int i = 4; i <= n; i++) {
            sb.append(' ').append(i);
        }
        System.out.println(sb.toString());
    }
}

n = int(input())
if n <= 2:
    print(-1)
else:
    res = [3, 2, 1] + list(range(4, n + 1))
    print(' '.join(map(str, res)))

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });
rl.on('line', (line) => {
    const n = parseInt(line.trim());
    if (n <= 2) {
        console.log(-1);
    } else {
        const res = [3, 2, 1];
        for (let i = 4; i <= n; i++) res.push(i);
        console.log(res.join(' '));
    }
    rl.close();
});

复杂度

  • 时间复杂度：，遍历输出排列。
  • 空间复杂度：（C++ 版本），（Java 用了 StringBuilder）。