Sengxian's Blog

题目地址

描述

Upper Bytown 和 Lower Bytown 的火车站被一条铁路连接着。火车从一侧到另一侧需要 $S(S\le {10}^9)$ 分钟。然而，每两列车发车时间至少需要间隔一分钟。并且，在每一个时刻，在铁路上的所有列车的行驶方向都必须相同。

有 $n(n\le {10}^6)$ 辆列车，列车的到站时间依次为 $t_1\le t_2\le \cdots\le t_n(t_i\le {10^9})$。这些火车将按照到站顺序，从 Upper Bytown 出发前往 Lower Bytown，到达后又需要回到 Upper Bytown。

请计算最迟回到 Upper Bytown 的列车回到 Upper Bytown 的时刻的最小值。

描述

为了叙述上的方便，下称左边是 Upper Bytown，右边是 Lower Bytown。

显然，在最优方案中，列车一定是一波一波连续的，即一波列车都到右边，然后依次回到左边，这就有一个 DP 的模型了，设 $f(i)$ 为第 $i$ 辆车回到左边的最早时刻。

问题来了，怎么转移？假设上一波的末尾是 $j$，这一波是 $(j, i]$，那么这一波的出发时刻就是 $f(j)$，发车有间隔一分钟的限制，如何快速计算列车 $i$ 的最早发车时刻呢，单单枚举 $j$ 已经是 $O(n^2)$ 的了，我们必须给出一个简洁的形式。

假设就从 $1$ 号车开始连续发车，我们计算出列车 $i$ 的最早发车时刻 $T(i)$，那么，刚才的问题中 $i$ 的最早发车时刻为：

至于正确性，需要从两个方面来证明。在这之前，我们先来做一个转换，求出了 $T(i)$，我们完全可以将 $i$ 的到站时刻就看做 $T(i)$，因为 $i$ 永远不可能在 $T(i)$ 之前发车，所以这个转换是没有影响的。

如果 $f(j) + i - j - 1 \ge T(i)$， 那么从 $f(j)$ 时刻开始，一定可以连续发 $i - j$ 辆车。

证明：假设不能连续发，那么必然存在一个最小的 $k \in (j, i]$，使得：

由于 $T(i) \ge T(i - 1) + 1$，我们得到：

矛盾，所以必然可以连续发车。

如果 $f(j) + i - j - 1 < T(i)$，那么 $i$ 号车必然可以在 $T(i)$ 时刻发完。

证明：不妨设 $f(j) \ge T(j + 1)$，找到第一个 $T(k)$ 大于 $f(j)$ 的位置 $k$，那么 $(j, k)$ 已经到站了，$[k, i]$ 还未到站。由于 $f(j) + i - j - 1 < T(i)$，所以 $[f(j), T(i))$ 这段时间内，一定有不少于 $i - j$ 个可以发车的时刻，那么我们可以先发 $(j ,k)$ 中的所有车，然后再发 $[k, i]$ 中的车。可以看出，一定有合法方案。

结合上面的证明，不难发现我们的式子的正确性，根据式子可以列出转移方程：

考虑分类讨论，去掉 $\max$：

我们可以通过各种技巧维护 $f(j) - j - 1$，然后做到 $O(n\log n)$ 求出答案。然而我们注意到，$f(j) - j$ 和 $T(i) - i$ 都是单调不降的，我们使用一个单调队列就可以解决问题。

复杂度：$O(n)$。

代码

//  Created by Sengxian on 2017/06/09.
//  Copyright (c) 2017年 Sengxian. All rights reserved.
//  BZOJ 3830 DP + 单调队列
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int readInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();
    return n;
}

const int MAX_N = 1000000 + 3;
const ll INF = 0x3f3f3f3f3f3f3f3fLL;
int n, S, t[MAX_N], tt[MAX_N];
int idx[MAX_N], q[MAX_N];
ll f[MAX_N];

int main() {
    n = readInt(), S = readInt();
    t[0] = -1;
    for (int i = 1; i <= n; ++i) {
        t[i] = max(readInt(), t[i - 1] + 1);
        tt[i] = t[i] - i;
    }

    int l = 0, r = 0, mx = 0;

    for (int i = 1, j = 0; i <= n; ++i) {
        f[i] = INF;
        while (r - l >= 1 && idx[q[l]] < i) mx = max(mx, q[l++]);

        if (mx != -1) f[i] = t[i] + S * 2LL + i - mx - 1;
        if (r - l >= 1) f[i] = min(f[i], f[q[l]] - q[l] * 2 + 2 * (S + i - 1));

        while (j <= n && tt[j] <= f[i] - i - 1) ++j;
        idx[i] = j - 1;

        if (idx[i] <= i) mx = max(mx, i);
        else {
            while (r - l >= 1 && f[q[r - 1]] - q[r - 1] * 2 >= f[i] - i * 2) --r;
            q[r++] = i;
        }
    }

    printf("%lld\n", f[n]);

    return 0;
}