[C++知识库]Educational Codeforces Round 133 (Rated for Div. 2) C. Robot in a Hallway

C. Robot in a Hallway

time limit per test: 2 seconds

memory limit per test:?256 megabytes

There is a grid, consisting of?22?rows and?mm?columns. The rows are numbered from?11?to?22?from top to bottom. The columns are numbered from?11?to?mm?from left to right.

The robot starts in a cell?(1,1)(1,1). In one second, it can perform either of two actions:

• move into a cell adjacent by a side: up, right, down or left;
• remain in the same cell.

The robot is not allowed to move outside the grid.

Initially, all cells, except for the cell?(1,1)(1,1), are locked. Each cell?(i,j)(i,j)?contains a value?ai,jai,j?— the moment that this cell gets unlocked. The robot can only move into a cell?(i,j)(i,j)?if at least?ai,jai,j?seconds have passed before the move.

The robot should visit all cells?without entering any cell twice or more?(cell?(1,1)(1,1)?is considered entered at the start). It can finish in any cell.

What is the fastest the robot can achieve that?

Input

The first line contains a single integer?tt?(1≤t≤1041≤t≤104)?— the number of testcases.

The first line of each testcase contains a single integer?mm?(2≤m≤2?1052≤m≤2?105)?— the number of columns of the grid.

The?ii-th of the next?22?lines contains?mm?integers?ai,1,ai,2,…,ai,mai,1,ai,2,…,ai,m?(0≤ai,j≤1090≤ai,j≤109)?— the moment of time each cell gets unlocked.?a1,1=0a1,1=0. If?ai,j=0ai,j=0, then cell?(i,j)(i,j)?is unlocked from the start.

The sum of?mm?over all testcases doesn't exceed?2?1052?105.

Output

For each testcase, print a single integer?— the minimum amount of seconds that the robot can take to visit all cells without entering any cell twice or more.

Example

input

4
3
0 0 1
4 3 2
5
0 4 8 12 16
2 6 10 14 18
4
0 10 10 10
10 10 10 10
2
0 0
0 0

output

5
19
17
3

思路：首先要明确的是走法要么就是绕整个矩形一圈，要么就是一开始“蛇形走位”，就是一列一列地走，比如从（0,0）开始到（1,0），再到（1,1），然后（0,1），再（0,2）……然后从某个格子开始把剩下的格子绕一圈，然后就好办了，维护一个数组b，表示从某一列开始绕圈所需要的时间，最后再结合前面的蛇形走位所需时间，进行比较，要是前面蛇形走位完加上后面格子的数量大于b（后面格子所需时间）则说明如果如果不算前面蛇形的格子的影响，那么后面每个格子的完成时间都是比较小的，因为即使有一个大了那就说明剩下的格子完成时间肯定都大了（毕竟至少也要花多一秒），因此不管前面怎样就直接选择b即为该方法的所需时间（不管前面有没有工作，到了某个地方还是要等）。

最后的最后，只能说自己真的脑子还不行，词不达意，这些话自己都组织了很久，可能也和自己的思维比较滞后有关系，但也只能这样了，下面还有一点注释。AC代码：

#include<bits/stdc++.h>
using namespace std;
//代码参考大神 Um_nik 
const int maxn=2e5+5;
int n,a[2][maxn],b[2][maxn],c[2][maxn];
int main()
{
	ios_base::sync_with_stdio(false),cin.tie(nullptr);
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<2;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin>>a[i][j];
			}
		}
		a[0][0]=-1;//为了方便参与后面的计算 
		b[0][n]=b[1][n]=0;
		for(int i=n-1;i>=0;i--)
		{
			for(int k=0;k<2;k++)
			{
				b[k][i]=max(max(a[1-k][i]+1,a[k][i]+2*(n-i)),b[k][i+1]+1);
				//这里计算的是从第k行第i列的那个元素开始向结尾处（列大的地方） 
				//再绕到另一行一直到第1-k行第i列那个元素，把这些任务全部完成所 
				//需要的时间，其中每次求解分为三块，一块是第k行第i列元素，一个 
				//是第1-k行第i列元素，再一个是除了这两个元素剩下的右边所有元素 
				//看哪个块需要“等”的时间比较长，比如第一个块的话则表示后面每 
				//完成一个cell都能进入下一个cell，即包括自己加上2*(n-i)即可完成 
				//所有的工作，而第二个块则是完成自己（+1），第三个块则是用上b， 
				//而b表示的是这个块做完的时间，因此也是+1（完成第二个块那个元素） 
			}
		}
		//最后再计算从某个一列开始停止蛇形走位，变成上面b所算的那种一个U弯的走法 
		//看哪个时间是最短的，至于算的方法就是维护一个cur（表示从开始蛇形走位到 
		//此列，后面U弯（并且假设后面不会停滞）所需要的时间）这个时间再和b去比较 
		//其中要是b大的话就说明后面还有阻拦，因此可以理解为阻拦之前的采取cur的 
		//到达某个格子的时间，阻拦后的则是采取b的时间（对每个格子取max），画图像 
		//把那些离散的点标出来就很好理解；若是cur大则说明后面毫无阻拦，因此取cur 
		//则是这个方法的真实所需时间。再根据这些时间去取到min则为最佳答案。 
		int ans=2e9,cur=0;
		for(int i=0;i<n;i++)
		{
			int k=i&1;//区分奇偶，U弯开始的行是不一样的，如0,0开始则为0行开始U弯 
			ans=min(ans,max(cur,b[k][i]));
			cur=max(cur,a[k][i]+2*(n-i));
			cur=max(cur,a[1-k][i]+2*(n-i)-1);
		}
		cout<<ans<<"\n";
	}
	
	return 0;
}