309670: CF1716C. Robot in a Hallway

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Robot in a Hallway

题意翻译

# Robot in a Hallway ## 题目描述 有一$ 2 $行$m$列的网格,从上到下编号为$1$至$2$,从左往右编号为$1$至$m$。 机器人开始时在网格$(1,1)$内。一秒内,它可以进行如下任意一个动作: - 走到上、下、左、右任意相邻的网格 - 待在网格内不动 开始时,除了网格$(1,1)$其他格子都是锁着的。每个网格$(i,j)$有一个值$a{i,j}$,表示该网格解锁的时间。只有经过至少$a_{i,j}$秒后,机器人才可以进入网格$(i,j)$。 机器人要走遍所有网格,且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。 实现如上操作的最快时间是什么? ## 输入格式 第一行是一个整数$ t $ ( $ 1 \le t \le 10^4 $ ),表示测试样例的个数。 每个样例的第一行是一个整数$ m $ ( $ 2 \le m \le 2 \cdot 10^5 $ ),表示网格的列数。 下面两行中的第$i$行有$m$个整数$ a_{i,1}, a_{i,2}, \dots, a_{i,m} $( $ 0 \le a_{i,j} \le 10^9 $ ),表示每个格子解锁的时间。$a_{i,1}=0$。如果$a_{i,j}=0$,表示网格$(i,j)$一开始就是解锁的。 所有测试样例中$m$的和不超过$2 \cdot 10^5$ ## 输出格式 对于每个测试样例,输出一个整数:机器人走遍每一个网格且每个网格只被访问一次的最小时间。

题目描述

There is a grid, consisting of $ 2 $ rows and $ m $ columns. The rows are numbered from $ 1 $ to $ 2 $ from top to bottom. The columns are numbered from $ 1 $ to $ m $ from left to right. The robot starts in a cell $ (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) $ , are locked. Each cell $ (i, j) $ contains a value $ a_{i,j} $ — the moment that this cell gets unlocked. The robot can only move into a cell $ (i, j) $ if at least $ a_{i,j} $ seconds have passed before the move. The robot should visit all cells without entering any cell twice or more (cell $ (1, 1) $ is considered entered at the start). It can finish in any cell. What is the fastest the robot can achieve that?

输入输出格式

输入格式


The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of testcases. The first line of each testcase contains a single integer $ m $ ( $ 2 \le m \le 2 \cdot 10^5 $ ) — the number of columns of the grid. The $ i $ -th of the next $ 2 $ lines contains $ m $ integers $ a_{i,1}, a_{i,2}, \dots, a_{i,m} $ ( $ 0 \le a_{i,j} \le 10^9 $ ) — the moment of time each cell gets unlocked. $ a_{1,1} = 0 $ . If $ a_{i,j} = 0 $ , then cell $ (i, j) $ is unlocked from the start. The sum of $ m $ over all testcases doesn't exceed $ 2 \cdot 10^5 $ .

输出格式


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.

输入输出样例

输入样例 #1

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

输出样例 #1

5
19
17
3

Input

题意翻译

# Robot in a Hallway ## 题目描述 有一$ 2 $行$m$列的网格,从上到下编号为$1$至$2$,从左往右编号为$1$至$m$。 机器人开始时在网格$(1,1)$内。一秒内,它可以进行如下任意一个动作: - 走到上、下、左、右任意相邻的网格 - 待在网格内不动 开始时,除了网格$(1,1)$其他格子都是锁着的。每个网格$(i,j)$有一个值$a{i,j}$,表示该网格解锁的时间。只有经过至少$a_{i,j}$秒后,机器人才可以进入网格$(i,j)$。 机器人要走遍所有网格,且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。 实现如上操作的最快时间是什么? ## 输入格式 第一行是一个整数$ t $ ( $ 1 \le t \le 10^4 $ ),表示测试样例的个数。 每个样例的第一行是一个整数$ m $ ( $ 2 \le m \le 2 \cdot 10^5 $ ),表示网格的列数。 下面两行中的第$i$行有$m$个整数$ a_{i,1}, a_{i,2}, \dots, a_{i,m} $( $ 0 \le a_{i,j} \le 10^9 $ ),表示每个格子解锁的时间。$a_{i,1}=0$。如果$a_{i,j}=0$,表示网格$(i,j)$一开始就是解锁的。 所有测试样例中$m$的和不超过$2 \cdot 10^5$ ## 输出格式 对于每个测试样例,输出一个整数:机器人走遍每一个网格且每个网格只被访问一次的最小时间。

Output

题目大意:
一个机器人位于2行m列的网格中,从上到下编号为1至2,从左到右编号为1至m。机器人开始时在网格(1,1)内,每秒可以进行如下任意一个动作:走到上、下、左、右任意相邻的网格,或者待在网格内不动。开始时,除了网格(1,1)其他格子都是锁着的,每个网格(i,j)有一个值a_{i,j},表示该网格解锁的时间。机器人要走遍所有网格,且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。求实现如上操作的最快时间。

输入数据格式:
第一行是一个整数t(1≤t≤10^4),表示测试样例的个数。
每个样例的第一行是一个整数m(2≤m≤2×10^5),表示网格的列数。
下面两行中的第i行有m个整数a_{i,1},a_{i,2},…,a_{i,m}(0≤a_{i,j}≤10^9),表示每个格子解锁的时间。a_{i,1}=0。如果a_{i,j}=0,表示网格(i,j)一开始就是解锁的。
所有测试样例中m的和不超过2×10^5。

输出数据格式:
对于每个测试样例,输出一个整数:机器人走遍每一个网格且每个网格只被访问一次的最小时间。题目大意: 一个机器人位于2行m列的网格中,从上到下编号为1至2,从左到右编号为1至m。机器人开始时在网格(1,1)内,每秒可以进行如下任意一个动作:走到上、下、左、右任意相邻的网格,或者待在网格内不动。开始时,除了网格(1,1)其他格子都是锁着的,每个网格(i,j)有一个值a_{i,j},表示该网格解锁的时间。机器人要走遍所有网格,且每个网格只能被访问一次(网格(1,1)在一开始就被访问过)。访问可以在任意网格内结束。求实现如上操作的最快时间。 输入数据格式: 第一行是一个整数t(1≤t≤10^4),表示测试样例的个数。 每个样例的第一行是一个整数m(2≤m≤2×10^5),表示网格的列数。 下面两行中的第i行有m个整数a_{i,1},a_{i,2},…,a_{i,m}(0≤a_{i,j}≤10^9),表示每个格子解锁的时间。a_{i,1}=0。如果a_{i,j}=0,表示网格(i,j)一开始就是解锁的。 所有测试样例中m的和不超过2×10^5。 输出数据格式: 对于每个测试样例,输出一个整数:机器人走遍每一个网格且每个网格只被访问一次的最小时间。

加入题单

上一题 下一题 算法标签: