题解：P13145 [GCJ 2018 #2] Falling Balls

阿尔萨斯 · 2025-08-25 11:12:59 · 题解

怀疑笔误

题面：“任意一个放有 \ 斜坡的格子左侧，绝不会紧挨着一个放有 / 斜坡的格子。”

这里应该是放有 \ 斜坡的格子的右侧不会紧挨着放有 / 斜坡的格子。

题意

给定 C 列底部的小球汇集数量，构造行数尽可能少的轨道，使得从每一列顶端向下扔一个球后，每一列底部汇集的小球数量等于规定情况。

分析

有解性

由于题目要求最左、右列不能安装轨道，因此最左、右列顶端的小球一定是径直落到底的，也就是说 B_i 和 B_C 一定要是 0，否则输出该情况无解。

除此之外，题目保证 B_i 的和等于 C，是否一定有解？是的，因为可以利用轨道将小球任意地调配。但这不那么直观，我来为你简单证明一下：

假设我要调配两个小球，且两个小球的运行路线不会穿过对方的路线，是否可行？可以，从两列的最上部开始搭建逐步变低的轨道，是互不干扰的，如下例，将 4 号小球调配到第 1 列，同时将 5 号小球调配到第 2 列：

...//.

..//..

.//...

假设我要调配两个小球，且两个小球的运行路线会穿过对方的路线，是否可行？穿过对方的路线是不可以的，因为轨道会交汇，然后小球就会卡住，也就是题面中所述的不合法情况；或者一条轨道被另一条轨道挡住了，见下例。但这很好解决，因为小球是等价的，并不规定汇集在每个位置的是具体哪些小球的话，只需要交换两个小球的目的地就可以转化成不穿过对方的情况了。证明的话，可以将两个小球的起点位置和终点位置，一共四个点看做梯形的四个顶点，那么总是可以放弃选择对角线而选择左右两条边，梯形左右两边不相交。
```
.\../.
..\/..
......
# 小球卡住了！
.\./.
../..
./.\.
.....
# 向右下的黑色轨道被向左下的蓝色轨道挡住了！
```

自此，我们证明完了，对于除了分析部分开头所说的那种无解情况之外的所有情况，我们都能找出一种分配方案，让小球的汇集情况和给定的情况一致。接下来就是求行数最小的分配方案了。

最优解

我们已经粗糙地证明了存在解，那就一定存在一个最优解（也许之一）。但，真的存在非最优解吗？可以发现，合法解是唯一的。具体来说，由于小球的分配安排不能穿过其他小球的分配安排，因此，解是唯一的。而且这个解很容易求得：将 B_i 中的 0 删去，剩下的数列就是分配方案。每次令尚未分配的前 B_i 个小球最终汇集在第 i 个 B_i 非零的位置即可。

实现

在上一节的最后一小节（“最优解”）中，分配方案已经说得很清楚了。注意到分配的区间（相信你注意到了由于分配的是连续的小球，它们的位置集合就是一个区间）不一定包含最终汇集位置。但这不是问题，因为只要分配路线不相交，解就是合法的。具体的，见下例：

B = {1, 0，1, 2}
.\\.
....

如果区间左端点在目标列左侧，则从区间左端点所在列的第一行开始，往右逐步往下安装右轨道；如果区间右端点在目标列右侧，则从右端点所在列的第一行开始，往左逐步往下安装做轨道。均直到列变为目标列时停止安装。最小合法行数就是安装轨道的最大行数加一（因为最底部要求有一行无轨道空行）。可以发现这样安装的轨道互不影响，空间利用效率最高，易证不存在更优解了。

实现不复杂，就不贴代码了吧。