题解：CF2246F Whoname and Unsorted Array
Cutest_Junior
·
·
题解
CF2246F 【Whoname and Unsorted Array】
题意
- 给定排列 p；
- 操作 i 可以把 [p_1\sim p_{i-1},p_i,p_{i+1},p_{i+2}\sim p_n] 变成 [p_i,p_1\sim p_{i-1},p_{i+2}\sim p_n,p_{i+1}]；
- 给原排列排序；
- 判断是否有解，若有解给出长度不超过 4n 的操作序列（可以证明有解时一定存在这样的序列）；
-
正解
操作 i 相当于把 p_{i+1} 移到末尾而 p_{i+2}\sim p_{n} 保持有序，考虑把 1\sim n 按顺序依次移到末尾。
假设当前已经完成了 1\sim x-1，即序列为 [\dots,1\sim x-1]，要把 x 移到末尾，找到 x 的位置 i，执行操作 i-1 即可。
例外是 i=1，因为无法执行操作 0。此时应先操作 2 把 x 移到位置 2，再操作 1 把 x 移到末尾，最后操作 n-1 把多余的数移出保证后缀连续。形如 [x,?,?,\dots,1\sim x-1]\rightarrow[?,x,\dots,1\sim x-1,?]\rightarrow[?,\dots,1\sim x-1,?,x]\rightarrow[?,?,\dots,1\sim x-1,x]。
例外是 x>n-2，此时不存在两个大于 x 的数字 ?，无法正常执行交换。又因为 i=1，仅剩两种情况，分别为 [n-1,n,1\sim n-2] 和 [n,1\sim n-1]。
第一种情况，先执行操作 1 把 n 移至末尾，再 n-2 次操作 n-1 把 n-2\sim1 依次移至开头即可。形如 [n-1,n,1\sim n-2]\rightarrow[n-1,1\sim n-2,n]\rightarrow[1\sim n-2,n-1,n]。
第二种情况，假设 n-2 为奇数，可以 n-2 次操作 2 把 n 移至位置 2，2\sim n-1 正好循环一遍位置不变，之后再执行操作 1 把 n 移至末尾即可。形如 [n,1,2\sim n-1]\rightarrow[1,n,2\sim n-1]\rightarrow[1,2\sim n-1,n]。
例外是 n-2 为偶数，此时序列逆序对数为 n-1（奇数），而任何操作都恰好改变 n-2 （偶数）对数的相对位置，逆序对数的变化量一定为偶数，最终一定无法让逆序对数为零（即排序好的状态）。
综上，完成有解判定并对有解情况完成排序。
最坏情况是归位 1\sim n-2 分别执行 3 次操作，归位 n-1 执行 1 次，归位 n 执行 n-1 次，一共 4n-6 次。时间复杂度 O(n^2)。