自动搬运

查看原文

来自洛谷，原作者为

	honglan0301 AFO —— 只是我的心一直在问，用什么把你永久留下～ | 2024.07.25 — ？

搬运于2025-08-24 22:44:28，当前版本为作者最后更新于2024-04-19 15:08:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析

<1> 首先不管空位数量的限制，先考虑如何让操作次数最少：

对每种颜色记录 二元组 $(x_i,y_i)\in\{(0,0),(0,1),(1,1)\}$ 表示颜色为 $i$ 的两辆车分别是/否位于靠近入口的一端，以及 $(u_i,v_i)$ 表示它们初始停放的车位编号。那么对 $(u_i,v_i)$ 连边建成图 $G$（形成若干个环与链），分讨可以得到操作次数的理论下界：

• $(x_i,y_i)=(0,0)$ 的颜色至少要进行一次操作。

• $(x_i,y_i)=(0,1)$ 的颜色，如果两辆该颜色的车已经配对则不用操作，否则至少进行一次操作。

  *特别地，当一个连通块中全是 $(x_i,y_i)=(0,1)$ 的颜色时，至少要多进行一次操作。因为连通块中第一个被操作的颜色不能立即完成配对。

• $(x_i,y_i)=(1,1)$ 的颜色至少要进行两次操作。因为车位是栈形的，我们无法在其中一辆车不动的情况下停放另一辆车。

再尝试构造方案：

• 首先把 $(x_i,y_i)=(1,1)$ 的颜色都换到初始局面的空位上。

• 此时图 $G$ 里每条链中的 $(x_i,y_i)$ 一定依次形如 $(1,0),(1,0),\dots,(1,0),(0,0)$，从前往后依次删即可；每个环中 $(x_i,y_i)$ 一定只有 $(1,0)$，任选一个 $1$ 换到空位处后，环变为链，用删链的方法即可。

• 因此能够找出操作次数达到理论下界的方案，sub2 得到了解决。

<2> 考虑在以上过程中，如何使得同一时刻占用车位数最少：

同样先分析下界，按照图 $G$ 各连通块的形态/状态分讨：

• 对于一条链。操作时，如果其中仅有 $(x_i,y_i)=(1,0)/(0,0)$ 的点，则对其操作时不需占用额外空位；否则至少要占用一个空位。操作后，空位数量增加 $1$（原先两端车位各只停一辆车）。

• 对于一个环。操作时，假如其中均有 $(x_i,y_i)=(1,0)$ 或只有一个 $(x_i,y_i)=(1,1)$，则至少占用一个空位；否则至少占用两个空位（因为对其进行任何操作后均会变成含有 $(1,1)$ 的链）。操作后，空位数量保持不变。

再构造/判无解：

• 首先操作不需额外空位的链。

• 此时若没有空位但仍需操作 则无解。

• 然后操作需要占 $1$ 个空位的链（因为能够提供新空位）。

  *具体地，我们从链头开始，每当碰到 $(x_i,y_i)=(1,1)$ 的颜色就将其换到空位处，并将其前面不含 $(1,1)$ 的链复原即可，占用空位数达到理论下界。

• 此时若空位数量为 $1$ 但存在需占用两个空位的环 则无解。

• 否则对环依次操作，即可在操作次数最少的前提下完成任务。

  *具体地，先把环上一个 $(x_i,y_i)=(1,1)$ 的颜色（如果没有就选 $(0,1)$ 的颜色） 换到空位处，之后即可按照链的方法操作，占用空位数能够达到理论下界。

综上，做完了。简单维护即可做到线性。

代码

丑陋的 赛时代码。