自动搬运

查看原文

来自洛谷，原作者为

	鏡音リン 希望大家都能成为自己想要的样子呐

搬运于2025-08-24 22:26:47，当前版本为作者最后更新于2020-12-05 19:36:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意：给定 $n+1$ 个栈，栈的高度限制为 $m$。初始时前 $n$ 个上每个有 $m$ 个球，最后一个为空。球分为 $n$ 种颜色，每种恰好 $m$ 个。一次操作可以把一个栈顶的元素弹出放到一个另一个栈顶，但是不可以使栈溢出或下溢。现要把同种颜色的球移动到同一个栈上，你需要构造一个在 $820000$ 次操作内的方案。

先来看通过这个操作都能干什么。例如，我们可以把一个满栈 $X$ 中所有颜色为 $y$ 的球挪到栈顶，这项操作需要借助另一个满栈 $H$ 和一个空栈 $N$：

1. 数一下 $X$ 中共有多少个颜色为 $y$ 的球，这个数字记为 $a$。
2. 把 $H$ 栈顶 $a$ 个元素依次放入 $N$。操作后 $H$ 有 $a$ 个空位，$N$ 有 $m-a$ 个空位。
3. 一直弹出 $X$ 的栈顶元素，如果颜色为 $y$ 则放入 $H$，否则放入 $N$，直到 $X$ 为空。这时 $H$ 和 $N$ 都恰好满了。
4. 把 $N$ 栈顶 $m-a$ 个元素依次放入 $X$，把 $H$ 栈顶 $a$ 个元素依次放入 $X$。这时 $X$ 中的元素还是原来的那些，不过顺序发生了变化，所有颜色为 $y$ 的都在栈顶。
5. 把 $N$ 全部 $a$ 个元素依次放入 $H$。操作后 $H$ 和 $N$ 恢复了操作前的原样。

这项操作的移动步数是 $2m+2a$。为了方便，我们把这个操作叫做“上提”。

有了这项操作，我们可以构造出一个算法：

1. 任选一个颜色 $y$，把所有 $n$ 个栈中颜色为 $y$ 的球都上提。
2. 把这些颜色是 $y$ 的球都移到那个空栈里。
3. 任选一个栈，把它的元素都移动到其他没满的栈里。
4. 去掉颜色是 $y$ 的球组成的栈，则问题规模 $n$ 减小了 $1$。回到第一步重新执行，直到 $n=1$ 结束。

这个算法的移动步数上界也容易分析。每次执行第一步的操作次数是 $(2n+2)m$，第二和第三步每一步是 $m$，合起来是 $(2n+4)m$。那么总体步数上界为 $\sum_{i=2}^n(2i+4)m=(n+6)(n-1)m$。

带入 $70$ 分部分分数据范围，算了一下这个数字是 $823200$，还差一点。于是……

潜在的常数优化方法：

• 上提操作的第三步，不需要把 $X$ 弹到空，只需要弹到里面没有颜色 $y$ 的球即可。
• 在上一条优化的基础上，算法的第一步，可以计算出上提每种颜色的球的代价，然后找一种最小的上提。
• 上提的第二步和第五步，如果 $m-a<a$，则只需要移动 $m-a$ 个元素，然后交换一下 $N$ 和 $H$ 的作用即可。

加上这些优化，$70$ 分到手。考虑正解。

考虑一个对两个栈的操作：给定栈 $X,Y$，重排两个栈的元素使得 $\operatorname{max}\{X\}\leq \operatorname{min}\{Y\}$。其中，$\operatorname{max}$ 和 $\operatorname{min}$ 都是针对颜色编号而言的。这个操作也需要借助另一个满栈 $H$ 和一个空栈 $N$。注意到同一种颜色可能有很多球，不便于操作，我们可以把所有元素分成“大的一半”和“小的一半”，分别应该装进 $Y$ 和 $X$ 里。以下我们用“元素为大”、“元素为小”称呼。

1. 数一下 $X$ 中共有多少个元素为大，这个数字记为 $a$。
2. 把 $H$ 栈顶 $a$ 个元素依次放入 $N$。操作后 $H$ 有 $a$ 个空位，$N$ 有 $m-a$ 个空位。
3. 一直弹出 $X$ 的栈顶元素，如果为大则放入 $H$，否则放入 $N$，直到 $X$ 为空。这时 $H$ 和 $N$ 都恰好满了。
4. 把 $N$ 栈顶 $m-a$ 个元素依次放入 $X$。
5. 一直弹出 $Y$ 的栈顶元素，如果为大则放入 $N$，否则放入 $X$，直到 $Y$ 为空。这时 $N$ 和 $X$ 都恰好满了。
6. 把 $N$ 栈顶 $m-a$ 个元素依次放入 $Y$，把 $H$ 栈顶 $a$ 个元素依次放入 $Y$。
7. 把 $N$ 全部 $a$ 个元素依次放入 $H$。操作后 $H$ 和 $N$ 恢复了操作前的原样。

为了方便下文管这个操作叫“切分”，意思当然是把小的一半切出来。操作结束时，$X$ 所有元素为小，$Y$ 所有元素为大。这就达成了我们的目的。这个操作的步数是 $4m+a\leq 5m$。可以使用类似上面第三条常数优化，如果 $m-a<a$，则第一步和第七步只需要移动 $m-a$ 个元素，然后交换 $H$ 和 $N$ 的作用即可。优化后移动次数不超过 $\frac{9}{2}m$。

注意到这个操作不适用于 $n=2$（因为压根就找不到可以用的 $H$），于是把 $n=2$ 特判出来，跑上面的算法。

有了这个操作，我们可以使用类似冒泡排序的方式把整个 $n$ 个栈按照颜色排序，排序之后很显然每个栈里球颜色一样。排序的正确性参照冒泡排序很容易证明（最大的元素一定会冒到最右边），可以算出移动步数 $\frac{9}{4}n(n-1)m$，渐进复杂度相同的情况下常数比上面那个算法大了一倍多，只能过 $40$ 分，看起来根本没用……

尝试换一种排序：归并排序。要解决的问题就是如何归并。类似普通归并的过程，维护两个指针 $x$ 和 $y$，初始值在要归并的两个区间最左侧。把两个指针指向的栈分别称为 $X,Y$。如果 $\operatorname{max}\{X\}<\operatorname{max}\{Y\}$，对 $X,Y$ 执行切分，小的一半放到 $X$，然后把指针 $x$ 递增，继续执行。否则把小的一半放在 $Y$，指针 $y$ 递增。这样做是正确的，因为未归并区间最小的 $m$ 个元素一定包含在了 $X$ 和 $Y$ 里。最后我们可以得到一系列从小到大的栈，不过它们并没有摆在它们应该在的位置上。于是归并的过程中记录一下每个栈应该在的位置，利用那个空栈进行整体移动，可以使用不超过 $2L$ 次整体移动把它们摆好（$L$ 是归并的区间长度）。于是，要归并一个长度为 $L$ 的区间，要执行不超过 $L$ 次切分和不超过 $2L$ 次整体移动，总操作次数不超过 $\frac{13}{2}Lm$。

由归并排序的复杂度证明得，所有归并的区间长度和是不会超过 $n\lceil\log_2n\rceil$ 的，于是这个算法的操作次数上界是 $\frac{13}{2}n\lceil\log_2n\rceil m$（很松，根本卡不满），算一下数字 $780000$，轻松过题。

还有一个优化，就是归并之后的“整体移动”其实是没必要的，可以用一个数组记录一下假装移动了，那么排序长度为 $L$ 的区间操作次数只有 $\frac{9}{2}Lm$，极限数据下总操作次数不会超过 $540000$。