P3580

lsj2009 · 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;
}