CF1716C Robot in a Hallway 题解

容易发现合法路径一定形如：先弯弯曲曲地走（即向下、向右、向上、向右地移动），再直接向右走到头，碰到边界后折回来。

所以考虑枚举弯曲地走的部分，这部分的最快时间容易求出。只需考虑快速求出剩余部分的最快时间，设对于第 \(i\) 第 \(j\) 列，这个时间为 \(f_{i, j}\)。

发现移动和等待格子解锁实质上可以描述为在平面上移动：若平面的 \(x\) 轴为路程，\(y\) 轴为时间，移动一步相当于 \(x \leftarrow x + 1, y \leftarrow y + 1\)；等待一秒相当于 \(y \leftarrow y + 1\)。这样得到的折线会分为很多段，为了方便处理，将一部分折线向上平移使得其构成一条直线，显然这样不会影响答案。（它的实际意义是在一开始就完成所有等待）这条直线的截距即为需要等待的时间。

求截距是一个常见套路：设走过的格子的解锁时间依次组成序列 \(t_1, t_2, t_3, \cdots t_m\)，则上述直线的截距为 \(\max\limits_{i = 1}^m \{ t_i - i \}\)。

于是容易求出剩余部分的最快时间 \(f_{i, j}\)，时间复杂度 \(O(n)\)。

#include <iostream>

#define int long long

using namespace std;

int n;
int a[2][200005];
int f[2][200005];

static inline int max(int x, int y, int z) { return max(max(x, y), z); }

static inline void solve() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> a[0][i];
    for (int i = 1; i <= n; ++i)
        cin >> a[1][i];
    a[0][1] = -1;
    f[0][n] = max(a[1][n] - 1, a[0][n]);
    for (int i = n - 1; i; --i)
        f[0][i] = max(f[0][i + 1] - 1,
                      a[1][i] - 2 * (n - i) - 1,
                      a[0][i]);
    f[1][n] = max(a[0][n] - 1, a[1][n]);
    for (int i = n - 1; i; --i)
        f[1][i] = max(f[1][i + 1] - 1,
                      a[0][i] - 2 * (n - i) - 1,
                      a[1][i]);
    int ans = min(f[0][1] + 2 * n, a[1][1] + max(0ll, f[1][2] - a[1][1] - 1) + 2 * n - 1);
    int sum = a[1][1] + 1;
    for (int i = 2; i <= n; ++i) {
        sum = max(sum, a[(i & 1) ^ 1][i]) + 1;
        sum = max(sum, a[i & 1][i]) + 1;
        ans = min(ans, sum + max(0ll, f[i & 1][i + 1] - sum) + 2 * (n - i));
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        solve();
    return 0;
}