同类题目：C语言自然序列重排——相邻元素的差值集合恰好有 k 个不同的值。⭐⭐-CSDN博客

题目描述（难度⭐）

一场针对 n 学生的考试将在一个又长又窄的房间里举行，因此学生们将按某种顺序排成一行。老师怀疑相邻编号的学生（i 和 i + 1）总是坐在一起学习，并成为朋友，如果他们在考试时坐在一起，他们肯定会互相帮助。 你的任务是选择最大数量的学生，并安排这些学生在教室里坐下，使得没有两个相邻编号的学生坐在一起。

输入

单独的一行包含一个整数 n（1 ≤ n ≤ 5000）— 考试中的学生数量。

输出

在第一行打印整数 k — 可以就坐的最大学生数量，使得没有两个相邻编号的学生坐在一起。 在第二行打印 k 个不同的整数 a1, a2, ..., ak（1 ≤ ai ≤ n），其中 ai 是第 i 个位置上的学生编号。相邻位置的学生不能有相邻的编号。

具体来说，对于从 1 到 k - 1 的所有 i，应该满足下面的条件：|ai - ai + 1| ≠ 1。 如果存在多个可能的答案，则输出其中任意一个。

如果存在多个可能的答案，则输出其中任意一个。 

样例输入

6

样例输出

6
1 5 3 6 2 4

 样例输入

3

样例输出

2

1 3

---

解题思路：通过特殊处理n≤3的情况，以及对n>3的情况根据n的奇偶性分别安排学生座位，使得没有两个相邻编号的学生坐在一起，同时尽量安排最多数量的学生。 

具体思路

1.处理n≤3的特殊情况：

◦ 当n=1时，只有1个学生，直接输出1个学生，编号为1。

◦ 当n=2时，有2个学生，只能选择1个学生，输出1个学生，编号为1。

◦ 当n=3时，有3个学生，可以选择2个学生，输出2个学生，编号为1和3。  

2. 处理n>3的一般情况：

◦ 定义一个数组arr，用于存储学生的编号，数组大小为n+1，将学生的编号1到n依次存储到数组中。

◦ 当n为偶数时：

        ■ 可以安排所有n个学生坐下。输出学生数量n。

        ■ 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2），这样就能保证相邻编号的                学生不会坐在一起。在输出时，注意最后一个学生编号后面不加空格，直接换行。  

◦ 当n为奇数时：

        ■ 也可以安排所有n个学生坐下。输出学生数量n。

        ■ 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2），这样就能保证相邻编号的                学生不会坐在一起。

        ■ 最后单独输出编号为n的学生。 

代码实现 （C语言版）

#include <stdio.h>

int main() {
    int n;
    scanf("%d",&n);  // 输入学生总数n
    // 处理n≤3的特殊情况
    if(n<=3)
    {
        // 当只有1个学生时，直接输出1个学生，编号为1
        if(n==1) printf("1\n1\n");
        // 当有2个学生时，只能选择1个学生，输出1个学生，编号为1
        if(n==2) printf("1\n1\n");
        // 当有3个学生时，可以选择2个学生，输出2个学生，编号为1和3
        if(n==3) printf("2\n1 3\n");
        return 0;  // 结束程序
    }
    int arr[n+1];  // 定义一个数组存储学生的编号
    // 将学生的编号1到n依次存储到数组中
    for(int i=1;i<=n;i++)
    {
        arr[i]=i;
    }
    // 当n为偶数时,2*(n/2)=n
    if(n%2==0)
    {
        printf("%d\n",n);  // 可以安排所有n个学生坐下，输出学生数量n
        // 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2）
        for(int i=1;i<=n/2;i++)
        {
            // 如果不是最后一个学生对，输出编号后加空格
            if(i!=n/2)
            printf("%d %d ",arr[i+n/2],arr[i]);
            // 如果是最后一个学生对，输出编号后直接换行
            else
            printf("%d %d\n",arr[i+n/2],arr[i]);
        }
    }
    // 当n为奇数时,2*(n/2)=n-1
    else
    {
        printf("%d\n",n);  // 也可以安排所有n个学生坐下，输出学生数量n
        // 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2）
        for(int i=1;i<=n/2;i++)
        {
            printf("%d %d ",arr[i+n/2],arr[i]);
        } 
        printf("%d\n",arr[n]);  // 最后单独输出编号为n的学生
    }
    return 0;
}

（C++版） 

#include <iostream>
#include <vector>

int main() {
    int n;
    std::cin >> n;  // 输入学生总数n
    // 处理n≤3的特殊情况
    if(n <= 3) {
        // 当只有1个学生时，直接输出1个学生，编号为1
        if(n == 1) std::cout << "1\n1\n";
        // 当有2个学生时，只能选择1个学生，输出1个学生，编号为1
        else if(n == 2) std::cout << "1\n1\n";
        // 当有3个学生时，可以选择2个学生，输出2个学生，编号为1和3
        else if(n == 3) std::cout << "2\n1 3\n";
        return 0;  // 结束程序
    }
    std::vector<int> arr(n);  // 定义一个vector存储学生的编号
    // 将学生的编号1到n依次存储到vector中
    for(int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    // 当n为偶数时
    if(n % 2 == 0) {
        std::cout << n << std::endl;  // 可以安排所有n个学生坐下，输出学生数量n
        // 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2）
        for(int i = 0; i < n / 2; i++) {
            // 如果不是最后一个学生对，输出编号后加空格
            if(i != n / 2 - 1)
                std::cout << arr[i + n / 2] << " " << arr[i] << " ";
            // 如果是最后一个学生对，输出编号后直接换行
            else
                std::cout << arr[i + n / 2] << " " << arr[i] << std::endl;
        }
    }
    // 当n为奇数时
    else {
        std::cout << n << std::endl;  // 也可以安排所有n个学生坐下，输出学生数量n
        // 通过循环，依次输出编号为i+n/2和i的学生（i从1到n/2）
        for(int i = 0; i < n / 2; i++) {
            std::cout << arr[i + n / 2] << " " << arr[i] << " ";
        } 
        std::cout << arr[n - 1] << std::endl;  // 最后单独输出编号为n的学生
    }
    return 0;
}

 法二（更巧妙）

代码思路：根据输入的整数 n，输出一个特定的序列：当 n <= 2 时输出 1 1，当 n == 3 时输出 2 1 3，当 n > 3 时先输出 n，然后依次输出所有偶数和奇数。

代码一（时间复杂度O（n））

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;  // 读取输入的整数 n

    // 处理 n <= 2 的情况
    if (n <= 2) {
        cout << 1 << endl;  // 输出 1
        cout << 1;        // 输出 1
    }
    // 处理 n == 3 的情况
    else if (n == 3) {
        cout << 2 << endl;  // 输出 2
        cout << 1 << " " << 3;  // 输出 1 3
    }
    // 处理 n > 3 的情况
    else {
        cout << n << endl;  // 输出 n
        // 输出所有偶数
        for (int i = 2; i <= n; i += 2) {
            cout << i << " ";
        }
        // 输出所有奇数
        for (int i = 1; i <= n; i += 2) {
            cout << i << " ";
        }
    }
    return 0;
}

代码二（时间复杂度为O（2*n）） 

#include<bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;  // 读取输入的整数 n

    // 处理 n <= 3 的特殊情况
    if (n <= 3) {
        // 如果 n <= 2，输出 1 1
        if (n <= 2) {
            cout << 1 << endl << 1;
        }
        // 如果 n == 3，输出 2 1 3
        else {
            cout << 2 << endl << 1 << " " << 3;
        }
        return 0;  // 结束程序
    }
    
    // 创建一个大小为 n 的向量 arr，并初始化为 1, 2, 3, ..., n
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = i + 1;
    }
    
    // 输出 n
    cout << n << endl;
    
    // 必须先输出奇数，再输出偶数
    // 先输出偶数再输出奇数会有特例，例如 n = 4 时，输出 2 4 1 3，不符合条件
    // 先输出奇数
    for (int i = 1; i < n; i += 2) {
        cout << arr[i] << " ";
    }
    // 再输出偶数
    for (int i = 0; i < n; i += 2) {
        cout << arr[i] << " ";
    }

    return 0;  // 结束程序
}