C. Robot in a Hallway(点击直达)

题目大意

有一个

2*m

的网格，一个机器人在

(1,1)

的位置，现在想要走遍所有的格子，且每个格子最多只能经过一次。

对于每个格子

(i,j)

存在

a_{i,j}

，表示至少经过

a_{i,j}

秒后才能进入这个格子。

每一秒内，机器人有两种动作；

求出走遍每一个格子的最小时间。

有

t

组数据:

1\leq t \leq 10^4

2 \leq m \leq 2 * 10^5

0 \leq a_{i,j} \leq 10^9

\Sigma m \leq 2 * 10^5

由题意易得有三种遍历方法

CPP

1 -> 2 -> 3 -> 4
			   |
8 <- 7 <- 6 <- 5

CPP

1 <- 8 <- 7 <- 6
|			   |
2 -> 3 -> 4 -> 5

CPP

1	 4 -> 5	   8
|	 |	  |    |
2 -> 3	  6 -> 7

假设所有

a

均为零，可以得出每种方法走到每个格子对应的时间

s1_{i,j}

，

s2_{i,j}

，

s3_{i,j}

，

接着，对于每种方法，遍历每个格子，对于任意

(i,j)

，求出其中

a_{i, j} - s_{i, j}

的最大值，即等待时间的最大值，若

a_{i, j} \leq s_{i, j}

,则按0算

求出三种方法对应的最大等待时间后，则可以假设开始时等待到某一时刻后，直接畅通无阻地走完格子。所以，对于每种方法，花费的时间为

2 * n - 1 + max(s_{i, j})

时间复杂度为

\Theta (n)

不知出于何种原因，WA2的1920样例，目前错误原因未知，求助