题意翻译
现在有一个长度为 $n$ 的数组 ${1,2,3,4,…,n}$ ,你每次操作可以交换其中任意两个数字的位置,但是要确保除了第一次交换是有两个数字不在原来的位置上外,后续每次操作之后只能增加一个不在原来位置上的数字(其实对应的就是题目中的 longest permutation chain
)
当所有数字都不在原来的位置时,操作结束
解题过程
首先根据题意,显然本题除了每组询问的 $chain$ 长度唯一外,操作过程并不唯一
题目其实就是要求我们构造一种操作使得符合上述题意
我这里采用的是先交换首位两个数字,再按照右左右左的顺序依次交换相邻两个数(因为第三组样例是)
貌似语言不好说明,那就举个例
$n$ 为奇数的例子
当 $n=5$ 时:
原始数组: $[1,2,3,4,5] \ \operatorname{fixedness}=5$
操作1: $[5,2,3,4,1] \ \operatorname{fixedness}=3$
操作2: $[5,2,3,1,4] \ \operatorname{fixedness}=2$
操作3: $[2,5,3,1,4] \ \operatorname{fixedness}=1$
操作4: $[2,5,1,3,4] \ \operatorname{fixedness}=0$
因此链长为 $5$
$n$ 为偶数的例子
$n=4$ 时:
原始数组: $[1,2,3,4] \ \operatorname{fixedness}=4$
操作1: $[4,2,3,1] \ \operatorname{fixedness}=2$
操作2: $[4,2,1,3] \ \operatorname{fixedness}=1$
操作3: $[2,4,1,3] \ \operatorname{fixedness}=0$
因此链长为 $4$
注意
不要漏了输出原始数组!
代码实现
1 |
|