自动搬运

查看原文

来自洛谷，原作者为

	Little_Cart 口号是赶森超载，优势是永远年轻

搬运于2025-08-24 23:04:20，当前版本为作者最后更新于2024-10-16 11:30:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

-1.前言

这道题开始真没思路，看了前一篇题解，茅塞顿开，也是给前一篇题解补充一点东西，再加上一点自己的东西。

前一篇题解把自己当成小推车，但是我就是小推车（Little_Cart）啊所以就来写一下

0.题意注意点

不可以卸下还装有饮料的瓶子，是指还装有饮料的瓶子剩余容量不会补充至 $p$。

同时，题意保证 $k \leq m$，这个其实挺重要的。

小推车开始是可以有饮料的，但是在题目中没有提到。

1.做法

上篇题解说到

题目中每个瓶子容积是一样的， 并且未空的瓶子不能重装饮料，这意味着可以预处理出来 $w[i]$ 代表到 $i$ 最少需要多少个空瓶子，$p[i]$ 表示到 $i$ 时去过去储藏室最多能装多少个空瓶子 ，$v[i]$ 表示 $i$ 到最近的储藏室并回到下一个服务位置的最小距离，$f[i]$ 表示服务 $1$ 到 $i$ 最少走的步数。

可以预处理原因很简单，首先是小推车他必须按照从 $1$ 到 $n$ 的顺序走，还有一个最主要的原因，就是只要这个瓶子放了这种饮料，那么直到他没有变空之前，这个瓶子只能一直是这个饮料。这个事情是不会根据选取的 $l$ 到 $r$ 的区间去改变的。

此时 $k \leq m$ 重要的原因也就明朗了，如果 $k>m$ 就有可能出现乘客要第 $m+1$ 种饮料，但是瓶子内部只有 $1$ 到 $m$ 的饮料，而且非空，这下子就上不去下不来卡在这里了。

预处理的方法也很简单，忽略加饮料需要去服务位置然后进行模拟即可。

$O(n^2)$ dp 只需要直接转移即可，dp 式子如下：

• $f_i=\min(f_j+v_j+i-j-1)$
• $w_i \leq q_j+w_j$

关于可以使用单调队列维护 dp 的原因我认为是因为原式可以转化成如下形式：

• $f_i=\min(val_j)+i$，其中 $val_j=f_j+v_j-j-1$。
• $w_i \leq q_j+w_j$

所以单调队列维护的就是这个 $val_j$。

由于这道题 $n$ 的最大值只有 $10^6$，所以可以直接使用优先队列维护，虽然多一个 $\log$ 的复杂度。