P8223题解

· · 题解

题解（moqueve）

我们定义一个数如果已经在自己最后的位置上，那么他的状态是 done；

我们考虑两种操作：

1、get，对于一个点，暴力地将其 done，一个数get代价约为 \dfrac{n}{x}+\dfrac{x}{2} \to 0​​​​​​​ 不等；

2、twin-swap，花 4​​ 的代价，同时交换两对距离为 2​​​ 的两个数，并不打乱其他数的顺序。以下给出一例：

取 x=6：
* * 1 3 2 5 4 6 * *
move(1,6,1):
5 * * 1 3 2 4 6 * *
move(5,10,0):
5 * * 1 2 4 6 * * 3
move(1,6,0):
* * 1 2 4 5 6 * * 3
move(5,10,1):
* * 1 2 3 4 5 6 * *

3、double-swap，花 8 的代价，依次交换两对距离为 2 的两个数，并不打乱其他数的顺序。以下给出一例：

取 x=6：
* * * 1 3 2 5 4 6
move(3,8,1):
* * 4 * 1 3 2 5 6
move(4,9,1):
* * 4 6 * 1 3 2 5
move(3,8,0):
* * 6 * 1 3 2 4 5
move(4,9,0):
* * 6 1 3 2 4 5 *
move(1,6,1):
2 * * 6 1 3 4 5 *
move(4,9,1):
2 * * * 6 1 3 4 5
move(1,6,0):
* * * 6 1 2 3 4 5
move(4,9,0):
* * * 1 2 3 4 5 6

注：以上两条仅在一定条件下成立；

于是，我们考虑进行以下步骤：

对于较小的数据规模，我们选择 x=2 暴力进行操作即可；

否则，我们选定一个偶数 x​；

首先我们前后依次 get，即先 get 1​，然后 n​，然后 2​，然后 n-1​……直到不能再归位为止；

然后对于中间的 x-1​ 个数 h \sim t，我们考虑：

如果存在两对逆序对，那我们直接用 twin-swap 交换即可；

否则，我们先用 double-swap 交换一对，此时：

如果操作到只剩最前面两个位置不对，我们对此 move(h,h+x-1,0)，然后进行 \dfrac{x-2}{2} 次 double-swap 操作即可。

这样差不多是 \dfrac{n^2}{2x}+\dfrac{nx}{2}+x^2+2x​​ 次，在 n=1000​​ 时取 x=30​​ 粗略估计约为 33000​ 次，精确一点差不多是 31650​ 次左右；​

但是，我们发现这玩意在随机数据下优秀许多；

所以，我们可以在开始添加 50​ 次随机循环位移，这样就降到了 25000​ 次以下；

我不知道怎么证明……但是我试了很多次都没超过 25000​ ……

但是实际上我们还可以优化：

我们发现在随机后由于总体位置改变不大，所以每次移动 x-1 位的期望次数不会怎么变，但是由于随机对最后平移一个点到指定位置的影响还是挺大的，期望只需要 \dfrac{nx}{4}，所以次数期望变成了 \dfrac{n^2}{2x}+\dfrac{nx}{4}+x^2+2x；

所以我们取 x=\sqrt{2\times n} 的时候次数还可以优化，降到了 23000 次以下；

时间复杂度 O(23n^2)​​​​。