题解 | 小红的排列构造①

#include <iostream>
#include <vector>
using namespace std;

// 不是质数：最简单的情况就是他是2的倍数，不包括2
// 要是2的倍数，需要奇数位配上奇数，偶数位配上偶数
// 但是有特殊情况:1号位不能从n中选择1，因为1+1=2为质数
// 解决方法就是对奇数位置进行循环左移操作:
// 1号位a1赋值3,3号位a3赋值5,5号位a5给到7...2*n-1号位给到1.
// 还有一个特殊情况是：n=1，n=2时均无解
// 核心要领：什么是循环左移，为什么要循环左移，怎么实现循环左移
int main() {
    int n;
    cin >> n;
    // odd = 1 3 5 7 9
    // p[odds[0]] = odd[ 1%5 ] -> position[1] = odd[1] = 3
    // p[3] = odd[ 2%5 ] -> position[3] = odd[2] = 5
    // p[5] = odd[3] = 7
    // p[7] = 9
    // p[9] = 1
    if (n == 1 || n == 2) {
        cout << -1;
        return 0;
    }
    vector<int> odds;
    vector<int> evens;
    for (int i = 1; i <= n; i++) {
        if (i % 2 != 0) {
            odds.push_back(i);
        }
        else {
            evens.push_back(i);
        }
    }
    vector<int> position(n+1);
    for (int i = 0; i < odds.size(); i++) {
        position[odds[i]] = odds[(i+1) % odds.size()];
    }   
    for (int i = 0; i < evens.size(); i++) {
        position[evens[i]] = evens[i];
    }
    for (int i = 1; i <= n; i++) {
        cout << position[i] << " ";
    }
    return 0;
}