关于c++的小小问题

Question

题目描述
Mas最近开始研究起了排列的奥秘，现在他一共有
1∼n共计
n个正整数，他想找出一种关于这
n个数的排列，使得当
k，满足
|ak-a(k-2)|=1
这样的排列被他成为
SYC排列，现在他想知道长度为
n的一个
syc排列
如果有多解，输出字典序最小的一种。
输入格式
输入第一行一个正整数
n，表示排列的长度

输出格式
输出字典序最小的长度为
n的
SYC排列
输入样例
3
输出样例
1 3 2
数据规模
对于
100%的数据，
n≤100000用c++怎么做？求各位指教！

Answer 1

🕒下午好，题主！目前：🟢[在线]
📢参考GPT-4o mini 模型、由清水白石008整理提供！
📣今日金句：“未来属于那些相信自己梦想之美的人。” — 埃莉诺·罗斯福

要生成一个长度为 ( n ) 的 SYC 排列，使得满足条件 ( |a_k - a_{k-2}| = 1 ) 的排列是字典序最小的，我们可以采用以下策略：

1. 理解 SYC 排列的性质：

   • 条件 ( |a_k - a_{k-2}| = 1 ) 意味着相邻的元素之间的差值必须为 1。
   • 这意味着我们可以通过交替选择较小和较大的数来构造排列。

2. 构造字典序最小的排列：

   • 我们可以将数字分为两部分：奇数和偶数。
   • 对于字典序最小的排列，我们可以先放置所有的奇数，然后再放置偶数。

3. 实现步骤：

   • 生成从 1 到 ( n ) 的所有数字。
   • 将奇数和偶数分开。
   • 按照奇数在前，偶数在后的顺序输出。

下面是 C++ 的实现代码：

#include <iostream>
#include <vector>

using namespace std;

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

    vector<int> result;

    // 添加奇数
    for (int i = 1; i <= n; i += 2) {
        result.push_back(i);
    }

    // 添加偶数
    for (int i = 2; i <= n; i += 2) {
        result.push_back(i);
    }

    // 输出结果
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) {
            cout << " ";
        }
    }
    cout << endl;

    return 0;
}

代码解释：

1. 输入：读取一个整数 ( n )。
2. 生成奇数和偶数：
   • 使用两个循环分别生成奇数和偶数，并将它们存储在 result 向量中。
3. 输出：遍历 result 向量，输出排列。

复杂度分析：

• 时间复杂度：( O(n) )，因为我们只需遍历 ( n ) 次来生成和输出排列。
• 空间复杂度：( O(n) )，用于存储结果。

这个方法确保了生成的排列是字典序最小的，并且满足 SYC 排列的条件。