自动搬运

查看原文

来自洛谷，原作者为

	lsj2009 关关雎鸠，在河之洲

搬运于2025-08-24 21:50:23，当前版本为作者最后更新于2023-10-29 11:09:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

至今没搞懂这个题为什么要单调队列……感觉这个题的题解写得都有些【数据删除】。

感觉说这题要有单调队列优化的题解都没搞清楚这题本质。

首先有个重要结论是：火车要么不回，要么一起回。

• 证明：首先如果回来的途中没有阻碍其他火车出现，那全部回来显然更优。那如果某个火车 $i$ 回来时没有阻碍其他火车发车，但是火车 $i+1$ 回来时会阻碍到其他火车发车，则每多回来一辆车，后一辆火车多延迟发车 $1$ 分钟，但是如果留到最后再回来，也会花费 $1$ 的时间，所以让他们一次性回来必然不比先把一部分放回来，最后再全部放回来劣。

根据此，我们考虑设计状态 $f_i$ 表示 $1\sim i$ 的火车全部过去且回来的最小代价。

题目保证了 $a_i$ 单调不减，为了防止 $a_{i-1}=a_i$ 而导致如果 $i-1$ 在 $a_i$ 出发后 $i$ 没法在 $a_i$ 时刻立刻出发，我们令 $a_i=\max\{a_{i-1}+1,a_i\}$。

则易得 $f_i=\min\limits_{j=0}^{i-1}\{\max\{f_j+i-j-1,a_i\}+2\times S+i-j-1\}$。

对于转移方程中那个 $\max$ 的含义：如果说途中没有那辆车是恰好卡着 $a_k$ 或者要等到 $a_k$ 再发车的，则 $j+1\sim i$ 全部到达 B 的时间取 $a_i+S$，否则取 $f_j+i-j-1+S$。

考虑 $\max$ 拆开，变换一下形式得：

$$f_i=\begin{cases} & \min\{-j\}+2\cdot S+a_i+i-1 \quad\quad f_j-j< a_i-i+1\\ & \min\{f_j-2\cdot j\}+2\cdot(S+i-1) \quad\quad f_j-j\ge a_i-i+1\\ \end{cases} $$

然后还有一个重要结论：$f_i\ge f_{i-1}+2$，感性理解是多了一辆车一去一回时间必然增加 $2$。

同时结合我们上面推导的东西，可以得到 $-j,f_j-2\cdot j$ 均有单调性。则得到，若 $k$ 为 $f_k-k< a_i-i+1$ 最后一个 $k$，则 $k$ 为第一种决策得最优决策点，$k+1$ 为第二种决策得最优决策点，同时因为 $f_k-k$ 和 $a_i-i+1$ 均有单调性，所以 $k$ 随 $i$ 得增大而随之增大，故而双指针即可，完全不用单调队列。

复杂度 $\Theta(n)$。

#include<bits/stdc++.h>
#define int long long
#define ll long long
#define ull unsigned long long
#define ld long double
#define PII pair<int,int>
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3f
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define rep(k,l,r) for(int k=l;k<=r;++k)
#define per(k,r,l) for(int k=r;k>=l;--k)
#define cl(f,x) memset(f,x,sizeof(f))
using namespace std;
const int N=1e6+5;
int f[N],a[N];
signed main() {
    int n,s;
    scanf("%lld%lld",&n,&s);
	a[0]=-1;
    rep(i,1,n)
        scanf("%lld",&a[i]),chkmax(a[i],a[i-1]+1);
    cl(f,0x3f); f[0]=0;
	int p=0;
    rep(i,1,n) {
        while(p<i&&f[p]-p<a[i]-i+1)
            ++p;
        chkmin(f[i],a[i]+2*s+i-(p-1)-1);
        if(p!=i)
            chkmin(f[i],f[p]+2*(i+s-p-1));
    }
    printf("%lld\n",f[n]);
    return 0;
}