题目链接:Problem - 1352G - Codeforces?
题意:给你一个数n,请你构造长度为n的排列(1-n中每个数字都要出现一次),使得相邻的两个数之间差的绝对值在2-4之间。
?
先看一下什么情况下我们无法构造出这样的序列。题目样例中2是已知无法构造的,我们尝试3,发现也无法构造,从4开始似乎每一个都可以构造。
我们尝试这是怎么构造出来的,当看到相差为2时,第一瞬间想到的是奇偶性相同的顺序序列
例如:
1,3,5,7,9......
2,4,6,8,10......
现在我们只用解决如何将这两个序列连接起来,因为相差为2-4,要求奇偶性不同,那么连接的这两个数就只能相差3,即用 9 - 3? 去连接,然后在从10输出,6和10相差为4,如果偶数最高项是8,那么就从8输出。不管是10还是8相差就在2-4区间内。
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n ;
void solve()
{
cin >> n ;
if(n <= 3) puts("-1") ;
else if(n == 4) puts("3 1 4 2 ") ;
else
{
for(int i = 1 ; i <= n ; i += 2)
cout << i << " " ;
int x , y ;
if(n % 2) x = n , y = n - 1 ;
else x = n - 1 , y = n ;
cout << x - 3 << " " ;
x -= 3 ;
for(int i = y ; i >= 2 ; i -= 2)
if(i != x) cout << i << " " ;
puts("") ;
}
}
signed main()
{
int t ;
cin >> t ;
while(t --)
{
solve() ;
}
return 0 ;
}