自动搬运

查看原文

来自洛谷，原作者为

	€€£ 中国收钱协会(€hina€ounting£oundation)唯一官方认证账号，有事欢迎@（有时候可能不在）||https://www.luogu.com.cn/paste/hm8t61yq

搬运于2025-08-24 22:37:04，当前版本为作者最后更新于2022-03-22 14:35:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解（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 交换一对，此时：

• 如果没有逆序对了，则交换 $h,h+1$；
• 如果还有逆序对，则交换这个逆序对；

如果操作到只剩最前面两个位置不对，我们对此 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)$​​​​。