题目一 神奇排列
给定正整数n，求一个长度为2n的数组，满足：
1 数组由 1 ~ 2n 共2n个数字打乱组成，且每个数字出现一次
2 每个偶数位（从0开始）和其右边的数字（奇数位上）的和组成的长度为n的新数组是一个公差为1的等差数列
输入：
- 第一行一个数字，test的次数
- 后面test行，每一行一个数字，为当前test的n
输出：
- 如果不能组成这样的2n长度数组，输出NO
- 如果可以，输出YES，并且打印数组
样例：
输入：
输出:
- YES
2 1
NO
YES
4 2 6 1 5 3
YES
6 3 8 2 10 1 7 5 9 4
这其实是一个技巧题。如果观察和稍加推导就发现：
1 偶数是一定会输出NO。因为中间的和会是一个.5的小数，整数凑不出来
2 所有的奇数，在前一半数组中奇数位的数字是n+1，后一半是n+2。我尝试证明，但是感觉有点点复杂。
3 既然这样，我们就写出来，在再验证看看。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| #include<bits/stdc++.h>
using namespace std;
void printarray(int n) {
for (int i = n + 1, j = 0; i <= 2 * n; i += 2) {
cout << i << " " << 2 * n + 1 - (n >> 1) + j - i << " ";
j++;
}
for (int i = n + 2, j = 0; j < (n >> 1); i += 2) {
cout << i << " " << 2 * n + 2 + j - i << " ";
j++;
}
cout << endl;
}
int main() {
int test = 0;
cin >> test;
while (test--) {
int n = 0;
cin >> n;
if (n % 2 == 0) {
cout << "NO" << endl;
}
else {
printarray(n);
}
}
}
|
对数器版
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
| #include<bits/stdc++.h>
using namespace std;
bool printarray(int n) {
int* processedarray = new int[2*n+1];
for (int i = 0; i <= 2*n; i++) {
processedarray[i] = 0;
}
for (int i = n + 1, j = 0; i <= 2 * n; i += 2, j++) {
int tmp = 2 * n + 1 - (n >> 1) + j - i;
processedarray[i] = processedarray[tmp] = 1;
}
for (int i = n + 2, j = 0; j < (n >> 1); i += 2, j++) {
int tmp = 2 * n + 2 + j - i;
processedarray[i] = processedarray[tmp] = 1;
}
for (int i = 1; i <= 2 * n; i++) {
if (processedarray[i] != 1) {
cout << "Oops!"<<n<<" is bad!" << endl;
for (int i = 0; i <= 2 * n; i++) {
cout<<processedarray[i]; }
return false;
delete[] processedarray;
}
}
delete[] processedarray;
return true;
}
int main() {
int test = 10000;
int n = 1;
bool continue1 = true;
while (test--&&continue1){
if (n % 2 == 0) {
}
else {
continue1 = printarray(n);
}
n += 2;
}
cout << "n = " << n << endl;
}
|
用暴力方法来gank，验证从1到2n，每一个数字是不是出现了，程序结果输出20001，意味着前n = 1~10000都是正确的，基本上是可以确定没毛病了。
