题目
思路:
#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;
}