Moe's CF Life

G. 特殊排列 (Special Permutation) - 猫娘的构造魔法喵~

哈喽，各位主人！今天我们来解决一道非常有趣的构造题，Codeforces 上的 1352G - Special Permutation。这道题需要我们动动小脑筋，找到一个特殊的排列方式，就像猫猫找到最舒服的姿势睡觉一样，喵~

题目大意

题目要求我们对于一个给定的整数 $n$ ( $n \ge 2$ )，找到一个长度为 $n$ 的排列 $p$ 。

什么是排列呢？一个长度为 $n$ 的排列就是一个包含了从 $1$ 到 $n$ 所有整数，并且每个整数都只出现一次的数组。比如说，[3, 1, 4, 2, 5] 就是一个长度为 5 的排列。

这道题对这个排列有一个特殊的要求：任何两个相邻元素的差的绝对值都必须在 2 和 4 之间（包括 2 和 4）。用数学语言来说，就是对于所有的 $i$ ( $1 \le i < n$ )，都要满足 $2 \le |p_i - p_{i+1}| \le 4$ 。

我们的任务就是，找到这样一个排列。如果找不到，就告诉裁判：“办不到啦，喵！”（也就是输出 -1）。

解题思路

一看到这种“找一个满足xx条件的xx”的题目，我们就应该想到，这很可能是一道 构造题 呢，喵。暴力搜索所有排列肯定是行不通的，因为 $n!$ 增长得太快啦，会累死猫的。所以，我们需要找到一个通用的“配方”，可以直接“烹饪”出符合要求的排列。

从小数据开始“侦查”

像猫猫一样，我们先从角落和缝隙（小数据）开始探索，看看能不能发现什么线索。

当 n = 2 时: 排列只有 [1, 2] 和 [2, 1]。它们的差的绝对值都是 |1-2| = 1，不满足 [2, 4] 的要求。所以不行，喵。
当 n = 3 时: 我们把所有 3! = 6 种排列都挠出来看看：
- [1, 2, 3] -> |1-2|=1 (不行)
- [1, 3, 2] -> |1-3|=2 (可以), |3-2|=1 (不行)
- [2, 1, 3] -> |2-1|=1 (不行)
- [2, 3, 1] -> |2-3|=1 (不行)
- [3, 1, 2] -> |3-1|=2 (可以), |1-2|=1 (不行)
- [3, 2, 1] -> |3-2|=1 (不行) 看来，n=3 的时候也找不到任何一个满足条件的排列。

所以，我们得出一个初步结论：当 $n \le 3$ 时，不存在这样的排列，应该输出 -1。

寻找通用构造“魔法” (n ≥ 4)

既然小数字不行，那大一点的数字呢？说不定对于所有 $n \ge 4$ 的情况，解总是存在的！我们来尝试构造一个通用的模式。

关键在于如何安排这些数字，让它们的差值不大不小。一个很自然的想法是把奇偶数分开，因为同奇偶性的数字之间相差至少是 2。

奇数组合：1, 3, 5, 7, ... 相邻两个数的差总是 2。
偶数组合：2, 4, 6, 8, ... 相邻两个数的差也总是 2。

这给了我们一个很好的思路！我们可以把所有的奇数放在一起，所有的偶数放在一起。但问题是，怎么把奇数组和偶数组连接起来呢？这个“接头”的地方是关键。

让我们尝试一个具体的方案：

先把所有奇数从大到小排列。例如 n=10 时，奇数部分是 9, 7, 5, 3, 1。它们之间的差都是 2，完美！
现在奇数部分的末尾是 1。我们需要从偶数中找一个数来接在 1 后面。
- 接 2？|1-2|=1，不行。
- 接 4？|1-4|=3，在 [2, 4] 范围内！看起来有戏！
- 接 6？|1-6|=5，不行。
好，我们决定用 4 来连接。现在排列是 [..., 3, 1, 4]。
4 后面接什么呢？我们还有偶数 2, 6, 8, 10 没用。
- 接 2？|4-2|=2，可以！
- 接 6？|4-6|=2，也可以！
这里的选择会影响后续。让我们试试题解里那种巧妙的方法：在 4 后面接 2。现在排列是 [..., 1, 4, 2]。
2 后面接什么呢？剩下的偶数是 6, 8, 10。
- 接 6？|2-6|=4，完美！
剩下的偶数 6, 8, 10, ...，我们按从小到大的顺序排列，它们之间的差也都是 2。

所以，我们的“魔法配方”诞生了，喵~

所有奇数倒序排列：[n或n-1, ..., 5, 3, 1]
一个神奇的“桥梁”：[4, 2]
剩下所有偶数正序排列：[6, 8, ..., n或n-1]

我们来验证一下这个构造的“接缝”处：

奇数序列的末尾 1 和 桥梁的开头 4：|1-4|=3，OK！
桥梁内部：|4-2|=2，OK！
桥梁的末尾 2 和 偶数序列的开头 6：|2-6|=4，OK！

这个构造方法在所有接缝处都满足条件，内部也满足条件。所以对于任何 $n \ge 4$ ，这个方法都是可行的！

举个例子，n=10:

奇数倒序: 9, 7, 5, 3, 1
桥梁: 4, 2
剩下偶数正序: 6, 8, 10 拼起来就是：9, 7, 5, 3, 1, 4, 2, 6, 8, 10。咦，和样例输出 9 6 10 8 4 7 3 1 5 2 不太一样。但是没关系！题目说的是输出 任何一个 符合条件的排列。我们的构造也是正确的！样例给的是另一种构造方法，但我们的方法更简单统一，喵~

题解代码

好啦，现在把我们发现的规律写成代码吧，就像猫猫把毛线球整理好一样~

cpp

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

void solve() {
    int n;
    std::cin >> n;

    // 对于 n <= 3 的情况，我们已经知道是不可能的，喵
    if (n <= 3) {
        std::cout << "-1\n";
        return;
    }

    std::vector<int> p;

    // 1. 放置所有奇数，从大到小
    // 就像猫猫从高处跳下来一样，一个一个来，喵~
    int start_odd = (n % 2 != 0) ? n : n - 1; // 找到不大于n的最大奇数
    for (int i = start_odd; i >= 1; i -= 2) {
        p.push_back(i);
    }

    // 2. 放置连接奇偶世界的魔法桥梁：4 和 2
    p.push_back(4);
    p.push_back(2);

    // 3. 放置剩下的偶数，从小到大
    // 然后我们再轻快地把剩下的偶数跳上去~
    for (int i = 6; i <= n; i += 2) {
        p.push_back(i);
    }

    // 打印出我们精心构造的排列
    for (int i = 0; i < n; ++i) {
        std::cout << p[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << "\n";
}

int main() {
    // 加速输入输出，让程序跑得像猫一样快
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

总结

这道题是一个典型的构造题。通过对小数据的分析，我们排除了 $n \le 3$ 的情况。对于 $n \ge 4$ ，我们发现了一个非常优雅的构造方法：倒序奇数 + [4, 2] 桥梁 + 正序偶数。这个方法简单且通用，能够轻松地解决问题。

希望这篇题解能帮到你，主人！下次再一起探索算法的奇妙世界吧，喵~

G. 特殊排列 (Special Permutation) - 猫娘的构造魔法喵~

题目大意

解题思路

从小数据开始“侦查”

寻找通用构造“魔法” (n ≥ 4)

题解代码

相关知识点介绍

1. 排列 (Permutation)

2. 构造算法 (Constructive Algorithms)

总结

G. 特殊排列 (Special Permutation) - 猫娘的构造魔法喵~ ​

题目大意 ​

解题思路 ​

从小数据开始“侦查” ​

寻找通用构造“魔法” (n ≥ 4) ​

题解代码 ​

相关知识点介绍 ​

1. 排列 (Permutation) ​

2. 构造算法 (Constructive Algorithms) ​

总结 ​

G. 特殊排列 (Special Permutation) - 猫娘的构造魔法喵~

题目大意

解题思路

从小数据开始“侦查”

寻找通用构造“魔法” (n ≥ 4)

题解代码

相关知识点介绍

1. 排列 (Permutation)

2. 构造算法 (Constructive Algorithms)

总结