题解：P10739 [SEERC2020] Disk Sort

Oct_ · 2024-07-22 10:51:25 · 题解

考虑一个思考方向：每次花费 \le 6 次操作排好一个颜色。

根据直觉，每次我们一定是选择移除目标颜色圆盘上的圆盘数尽可能少的颜色，这样我们清理上方比较方便。

对与一种颜色，设 [a,b,c] 表示其三个位置的深度（由上到下深度依次为 0,1,2）。注意到一个结论，就是一定存在一个 [a,b,c] 使得 a+b+c \le 3。而除 [1,1,1] 外的所有这样的情况都可以通过 \le 6 次操作，得到一个新排好序的柱子。

然而我们发现除去 [1,1,1] 并没有影响，因为总会存在一个颜色是满足至少一个圆盘在顶上。

如果每次都找一个这样的颜色，将其排序，一共需要 6(n-1) 次（最后一种颜色会在最后自然排好）。花费 3 次将最后一个柱子清空。

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

如果不想写长，可以考虑 [a,b,c] 应满足 a \le 0,b \le 1。这样可以快速方便地找到可操作的颜色。我们目标明确地将目标圆盘都移到空柱子上，然后记录一下除空柱子外的空位就能简单地移除上方的障碍了，不用考虑两个目标圆盘在同一个柱子上的情况。