题解：P11833 [省选联考 2025] 推箱子

cff_0102 · 2025-03-06 21:11:35 · 题解

提供一种全新的可并堆做法，也是我考场上想到的做法（虽然当时没调出来）。

首先，可以倒着考虑整个过程：想象时间倒着流动到零，第 i 个箱子刚开始在 b_i，当时间流动到 t_i 时才可以开始移动，当时间回到 0 时，它需要位于 a_i。

根据这个想法，可以首先将所有箱子按 t 从大到小排序。至于当 t 相同时如何处理稍后再说。

这样，就会发现，每到达一个新的 t_i 时，就有（至少）一个新的箱子可以移动，而“先前”因为被这个箱子挡住的其它箱子也在此时才可以开始继续往 a_i 的方向移动。

因此可以开一个数组 mov，mov_i 表示有几次移动是在（排序后的）t_i 这个时刻“开始后”才可以进行的。不难发现得出这个数组后，具体每次移动的顺序是不重要的，因为总是可以找到一种移动的方法使每一步（如果还需要的话）都可以让一个箱子往“终点”的方向移动。

只要知道了这个数组的值，接下来判断是否有解就简单了：贪心地让每次尽量让每个操作都靠前进行，如果最后到 0 时刻还有操作需要进行则无解，否则有解。

代码片段：

for(int i=1;i<=n;i++){
    int x=mov[i];
    mov[i]=min(mov[i],a[i].t-a[i+1].t);
    x-=mov[i];
    mov[i+1]+=x;
}
if(mov[n+1]){
    cout<<"No\n";
}else{
    cout<<"Yes\n";
}

接下来问题就是怎么搞出 mov 数组了，首先可以想到一个 n^2 暴力跳的方法：

仍然是按照时间从后到前遍历每个箱子（后面的编号都指按时间从大到小排序后的编号）。遍历到第 i 个箱子时，此时它应该仍然处在 b_i 的位置，要前往 a_i。为了方便，先假设 a_i>b_i。首先对于每个箱子预处理出它后面第一个时间“晚于”它（实际上是 t 比它更小）的箱子的编号。那么就可以找到箱子 i 后面第一个从时间上看可能会挡住它的箱子 x，再判断它是否会挡住这个箱子。

• 如果会挡住，那么 i 就还需要等待到 x 号箱子可以移动后才可以继续前进。此时就将 mov_i 增加移到 x 号箱子前的步数，然后假设当前箱子移到了 x 号箱子的位置，并继续考虑当 x 号箱子可以动之后应该怎么继续往前走，再修改 mov_x，一直这样往后跳箱子。
• 直到右边的那个箱子 x 不会挡住当前的箱子 i，也就是现在 i 可以直接移动到 a_i 了，那么就给 mov_x 增加这次移动需要的步数，并结束循环。