政府网站建设工作存在的不足首页关键词排名

1、题目

G. Special Permutation

这道题的意思是给我们从$1$到$n$的排列，然后我们对这个排列的顺序上进行调换，需要满足的条件是任意两个相邻元素的绝对值的差满足条件：$2\le |p_i-p_{i+1}|\le 4$

2、分析

我们很容易发现，如果我们把奇数放在一起，偶数放在一起，那么对于这两部分而言，内部相邻的元素必定是满足条件的。

现在的问题是奇数部分和偶数部分之间衔接的地方，我们需要让这个地方也满足条件。因此，我们可以将奇数从大到小枚举，那么最后一

个奇数就一定是$1$。为了保证偶数和$1$的差值的绝对值是大于等于$2$的，我们就不能在$1$的右面放$2$。所以我们可以在$1$的右面放$4$。在$4$的右

面放$2$，$2$的后面放$6$。$6$后面按照升序枚举剩余的偶数即可。

根据上面的条件可以知道，我们必须得有$4$才行。所以如果我们的$n$是比$4$小，就无法构造出符合条件的序列，反之即可以构造。

3、代码

#include<bits/stdc++.h>
using namespace std;void solve()
{int n;cin >> n;vector<int>v(n);if(n < 4){cout << -1 << endl;return;}for(int i = n; i > 0; i --){if(i % 2)cout << i << " ";}cout << 4 << " ";for(int i = 2; i <= n; i ++ ){if(!(i % 2) && i != 4){cout << i << " ";}}cout << endl;return;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while(t --)solve();
}