[CF1741B]Funny Permutation 题解

我的个人博客

思路

题目要求任意一个数要和最少相邻一个数相差为 $ 1 $ ,我们可以很简单地想到构造两个序列:由 $ 1 $ 到 $ n $ 正序构造序列，和由 $ n $ 到 $ 1 $ 倒序构造序列，那么这两个序列一定符合题目中的第一个要求。正序的序列在每一个位置上都违反了第二个要求,所以我们放弃正序构造序列。

对于第二个倒序序列，由于它是倒序的，那么在大部分位置(除了最中间)，都有 $ i \not= n-i+1 $,其中他的下标为 $ i $ ,值为 $ n-i+1 $ 。因为:

• 当 $ n $ 为偶数的时候， $ 2 \times i + 1 = n $ 恒不成立，通过奇偶性可以得知。
• 当 $ n $ 为奇数的时候， $ 2 \times i + 1 = n $ 会在 $ i = (n - 1) \div 2 $ 时成立

于是，对于 $ n $ 为偶数时，我们直接输出倒序序列即可。对于 $ n $ 为奇数的时候，我们要避免在 $ i = (n - 1) \div 2 $ 的位置上填入 $ (n - 1) \div 2 $ ，于是我们将序列分为两半部分，在 $ i < (n - 1) \div 2 $ 时按照倒序的方法输出，在$ i \geq (n - 1) \div 2 $，将倒序的序列再次倒序输出，也就是说在 $ (n - 1) \div 2 $ 的位置上我们填入 $ 1 $，接下来依次填入$ 2,3,4,5 \dots $ ，因为$ i \geq (n - 1) \div 2 $ 的值已经在前面填入过了，所以一定不会出现 $ i = p_i $的情况。

但是， $ n = 3 $是一个特殊的情况，因为此时 $ i < (n - 1) \div 2 $ 的部分只有一个数，即 $ p_1 = 3$ ，他相邻的另外一个数 $ p_2 $ 只能为 $ 1 $，所以此时没有任何一种情况可以构造出一个“有趣的排列”，输出 $ -1 $。我们可以证明其他时候是不会出现构造不出来“有趣的排列”的，因为当 $ n $ 为偶数的时候可以直接输出逆序序列， $ n $ 为奇数时，除去 $ n = 3 $ 的情况， $ n \geq 5 $，那么 $ (n - 1) \div 2 \geq 2 $，前半部分至少有两个数是逆序输出的，符合第一条要求。于是输出 $ -1 $ 只需要特判 $ n $ 是否为 $ 3 $就可以了

代码

#include<bits/stdc++.h>
using namespace std;
int t,n;
int main(){
	cin>>t;
	while(t--){
		cin>>n;
		if(n == 3){
			cout<<-1<<endl;
			continue;
		}
		if(n % 2 == 0){
			for(int i = n;i >= 1;i--){
				cout<<i<<" ";
			}
			cout<<endl;
		}else{
			for(int i = n;i > (n-1)/2 + 1;i--){
				cout<<i<<" ";
			}
			for(int i = 1;i < n - (n-1)/2 + 1;i++){
				cout<<i<<" ";
			}
			cout<<endl;
		}
	}
	return 0;
}