Educational Codeforces Round 133 (Rated for Div. 2) C. Robot in a Hallway

题目

思路：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define lson p << 1
#define rson p << 1 | 1
const int maxn = 1e6 + 5, inf = 1e18, maxm = 4e4 + 5;
const int N = sqrt(1e9) + 1;
 const int mod = 1e9 + 7;
// const int mod = 998244353;
//const __int128 mod = 212370440130137957LL;
// int a[505][5005];
// bool vis[505][505];
 
int a[2][maxn], b[maxn];
bool vis[maxn];
string s;
int n, m;
 
struct Node{
    int val, id;
    bool operator<(const Node &u)const{
        return val < u.val;
    }
};
// Node c[maxn];
 
int ans[maxn];
int pre[maxn];
 
int f[maxn][2]; //f[j][i]为从起点开始，蛇皮走位到第j列，第i行的最长等待时间
int g[maxn][2];//g[j][i]为从（i，j）向右开始钩子走位，最后回到（i ^ 1, j)的最长等待时间
//long long ? maxn ? n? m?
void solve(){
    int res = 0;
    int q, k;
    cin >> m;
    // int mx = 0, mn = inf;
	for(int i = 0; i < 2; i++){
		for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    //设在起点等待时间为t，到达(i, j)是第k个到达的格子，那么若t + k >= a[i][j] + 2 - k，
    //(题解为t + k >= a[i][j] + 1, 是因为最后题解答案 + 2 * m，实际是2 * m - 1)
    //则在起点等待t秒后，不考虑其他格子的话，可以顺利到达格子(i, j)
    f[0][0] = f[0][1] = -inf;
    f[1][0] = 0;//起点比较特殊，不适用 t + k >= a[i][j] + 2 - k, 单独更新
    f[1][1] = a[1][1] + 2 - 2;//顺便更新掉
    g[m + 1][0] = g[m + 1][1] = -inf;
    for(int j = 2; j <= m; j++){
        f[j][j % 2] = max({f[j - 1][(j - 1) % 2], a[j % 2][j] + 2 - 2 * j, a[j % 2 ^ 1][j] + 2 - (2 * j - 1)});
        // cout << j << ' ' << j % 2 << ' ' << f[j][j % 2] << '\n';
    }
    
    for(int i = 0; i < 2; i++){
        for(int j = m; j >= 2; j--){//注意j >= 2, 因为当j == 1时，整个路径为钩子，就牵扯到起点，得单独更新
            g[j][i] = max({g[j + 1][i] - 1, a[i][j] + 2 - 1, a[i ^ 1][j] + 2 - 2 * (m - j + 1)});
            // cout << j << ' ' << i << ' ' << g[j][i] << '\n';
        }
    }
    res = inf;
    for(int j = 1; j <= m; j++){
        int tmp = max({0LL, f[j][j % 2], g[j + 1][j % 2] - 2 * j});//拼接 蛇和钩子
        res = min(res, tmp);
    }
    res = min(res, max({0LL, g[2][0] - 1, a[1][1] + 2 - (2 * m)}));//考虑整个路径为钩子的情况
    cout << res + 2 * m - 1 << '\n';
}   
    
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T = 1;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}