C语言/C++自然序列重排列——相邻序号不相邻问题⭐

同类题目：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个学生，编号为1if(n==1) printf("1\n1\n");// 当有2个学生时，只能选择1个学生，输出1个学生，编号为1if(n==2) printf("1\n1\n");// 当有3个学生时，可以选择2个学生，输出2个学生，编号为1和3if(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)=nif(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]);// 如果是最后一个学生对，输出编号后直接换行elseprintf("%d %d\n",arr[i+n/2],arr[i]);}}// 当n为奇数时,2*(n/2)=n-1else{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个学生，编号为1if(n == 1) std::cout << "1\n1\n";// 当有2个学生时，只能选择1个学生，输出1个学生，编号为1else if(n == 2) std::cout << "1\n1\n";// 当有3个学生时，可以选择2个学生，输出2个学生，编号为1和3else 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] << " ";// 如果是最后一个学生对，输出编号后直接换行elsestd::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;  // 输出 1cout << 1;        // 输出 1}// 处理 n == 3 的情况else if (n == 3) {cout << 2 << endl;  // 输出 2cout << 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 1if (n <= 2) {cout << 1 << endl << 1;}// 如果 n == 3，输出 2 1 3else {cout << 2 << endl << 1 << " " << 3;}return 0;  // 结束程序}// 创建一个大小为 n 的向量 arr，并初始化为 1, 2, 3, ..., nvector<int> arr(n);for (int i = 0; i < n; i++) {arr[i] = i + 1;}// 输出 ncout << 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;  // 结束程序
}