神奇的排列 - 算法题解/n/n## 题目描述/n/n对于一个长度为 2n 的排列 p_1,p_2,...,p_{2n}，定义数组 s 为 p 中两两分组以后每个组的数字之和，即 s_i=p_{2i-1}+p_{2i}，可以发现 s 的长度为 n。若 s 是一个连续严格递增数列，则我们称排列 p 为一个神奇的排列。/n/n现在我们给定一个数字 n ，请给出一个长度为 2n 可能的神奇的排列 p。/n/n## 输入格式/n/n第一行一个数字 T，代表有 T 组数据。/n/n接下来 T 行，每行一个整数 N。/n/n## 输出格式/n/n如果存在满足题意的排列，请输出 YE5，并且在下一行输出一个可能的排列。如果不存在，请输出 N0。/n/n## 样例 #1/n/n### 样例输入 #1/n/n/n3/n1/n2/n5/n/n/n### 样例输出 #1/n/n/nYE5/n2 1/nN0/nYE5/n6 3 8 2 10 1 7 5 9 4/n/n/n## 提示/n/n数据范围/n/n对于 10% 的数据，N 全为偶数。 /n对于另外 30% 的数据，T=1。 /n对于 60% 的数据，1/leq T /leq 50，N/leq500。 /n对于 100% 的数据，1/leq T /leq 500，1/leq N /leq 10^5，且每组数据中，∑ N /leq 10^5。/n/n提示/n/n排列：长为 N 的排列指的是由 1 ~ N 组成的数列，比如 N=3 的排列有：1 2 3、1 3 2、2 1 3、2 3 1、3 1 2、3 2 1等共 6 个。/n/n连续严格递增数列：对于整个数列都有第 i 个数字 a_i 和第 i+1 个数字 a_{i+1} ，a_{i+1}=a_i+1./n/n## 代码实现/n/ncpp/n#include <iostream>/n#include <vector>/n/nusing namespace std;/n/n// 判断是否是连续严格递增数列/nbool isIncreasing(vector<int>& s) {/n int n = s.size();/n for (int i = 0; i < n - 1; i++) {/n if (s[i + 1] - s[i] != 1) {/n return false;/n }/n }/n return true;/n}/n/nint main() {/n int T;/n cin >> T;/n while (T--) {/n int N;/n cin >> N;/n if (N % 2 != 0) {/n cout << /'N0/' << endl;/n continue;/n }/n vector<int> p(N);/n // 构造一个神奇的排列/n for (int i = 0; i < N; i += 2) {/n p[i] = N - i;/n }/n for (int i = 1; i < N; i += 2) {/n p[i] = i;/n }/n // 计算数组s/n vector<int> s(N / 2);/n for (int i = 0; i < N / 2; i++) {/n s[i] = p[2 * i] + p[2 * i + 1];/n }/n if (isIncreasing(s)) {/n cout << /'YE5/' << endl;/n for (int i = 0; i < N; i++) {/n cout << p[i] << /' /';/n }/n cout << endl;/n } else {/n cout << /'N0/' << endl;/n }/n }/n return 0;/n}/n/n/n该算法的思路是先构造一个满足题意的排列，然后判断排列中的数组s是否是连续严格递增数列。算法的时间复杂度为O(N)。/n