CF2275E.Repentance Is Already on the Way
普及/提高-
通过率:0%
时间限制:2.00s
内存限制:256MB
AC君温馨提醒
该题目为【codeforces】题库的题目,您提交的代码将被提交至codeforces进行远程评测,并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供,我们无法保证该服务的稳定性,若提交后无反应,请等待一段时间后再进行重试。
题目描述
Because of K1o0n's friend Gorilla's rampage, the two main parallel roads were blocked in city X. Now the residents have to use the old roads connecting the city's buildings.
Along each main road there are n buildings. The buildings on the first road belong to companies a1,a2,…,an. The buildings on the second road belong to companies b1,b2,…,bn. One company may own several buildings.
The old roads are arranged as follows:
- buildings ai and bi are connected by a road;
- buildings ai and bi+1 (i+1≤n) are connected by a road;
- buildings ai and bi−1 (2≤i) are connected by a road.
All old roads are bidirectional. There are no other available roads in the city.
A road between buildings of the same company has length 2 kilometers. A road between buildings of different companies has length 1 kilometer.
K1o0n decided to personally drive around the city and assess the consequences of his friend's mischief. He starts at building a1 and wants to visit each of the 2n buildings exactly once. He may finish the trip at any building.
To make Gorilla think carefully about his behavior, K1o0n took him along and decided to choose the longest route. Find the maximum possible length of their route.
由于 K1o0n 的朋友 Gorilla 的肆意破坏,城市 X 的两条主干道被封锁了。如今,市民不得不使用连接城市各栋建筑的旧道路。
每条主干道上各有 n 栋建筑。第一条主干道上的建筑分别属于公司 a1,a2,…,an;第二条主干道上的建筑分别属于公司 b1,b2,…,bn。同一家公司可能拥有多个建筑。
旧道路的连接方式如下:
- 建筑 ai 与 bi 之间有一条道路;
- 建筑 ai 与 bi+1(满足 i+1≤n)之间有一条道路;
- 建筑 ai 与 bi−1(满足 2≤i)之间有一条道路。
所有旧道路均为双向通行。城市中不存在其他可用道路。
连接同一家公司所属建筑的道路长度为 2 千米;连接不同公司所属建筑的道路长度为 1 千米。
K1o0n 决定亲自驾车绕城一圈,评估其朋友恶作剧所造成的后果。他从建筑 a1 出发,希望恰好访问全部 2n 栋建筑一次(即构成一条哈密顿路径),终点可以是任意一栋建筑。
为了让 Gorilla 认真反思自己的行为,K1o0n 带上了他,并决定选择最长的可行路线。求该路线的最大可能总长度。
输入格式
The first line contains an integer t (1≤t≤104) — the number of testcases.
The first line of each testcase contains an integer n (1≤n≤2⋅105) — the number of buildings on each main road.
The second line of each testcase contains n integers a1,a2,…,an (1≤ai≤109) — the buildings on the first main road.
The third line of each testcase contains n integers b1,b2,…,bn (1≤bi≤109) — the buildings on the second main road.
It is guaranteed that the sum of n over all testcases does not exceed 2⋅105.
第一行包含一个整数 t(1≤t≤104)——测试用例的数量。
每个测试用例的第一行包含一个整数 n(1≤n≤2⋅105)——每条主干道上的建筑物数量。
每个测试用例的第二行包含 n 个整数 a1,a2,…,an(1≤ai≤109)——第一条主干道上的建筑物高度。
每个测试用例的第三行包含 n 个整数 b1,b2,…,bn(1≤bi≤109)——第二条主干道上的建筑物高度。
保证所有测试用例的 n 之和不超过 2⋅105。
输出格式
For each testcase, output one integer — the longest route that K1o0n can take Gorilla on.
对于每个测试用例,输出一个整数——K1o0n 能带大猩猩走的最长路径长度。
输入输出样例
输入#1
5 1 5 5 4 1 2 3 4 1 9 2 3 5 7 7 7 7 7 7 7 7 7 7 5 1 3 2 4 5 2 3 5 2 4 2 1 2 1 2
输出#1
2 10 18 12 5
说明/提示
In the second testcase, one can construct the route shown in the picture. Its length is 10 kilometers. It can be shown that a longer route is impossible.
Second testcase.
In the third testcase, no matter which route you choose, Gorilla will suffer with K1o0n for the entire 18 kilometers of the road.
在第二个测试用例中,可以构造如图所示的路线,其长度为 10 千米。可以证明,不存在更长的路线。
第二个测试用例。
在第三个测试用例中,无论选择哪条路线,大猩猩都将与 K1o0n 一同承受整条 18 千米道路的煎熬。
输入解题思路,AI测评打分。不知道怎么写?