← 返回题目列表

Codeforces · 1506/F

F. 三角形路径

中文机器翻译题面 查看原题

考虑一个由层组成的无限三角形。让我们从三角形的顶部(从上到下)对层进行编号,从一层开始。三角形的第 $$$k$$$ 层包含 $$$k$$$ 点,从左到右编号。无限三角形的每个点都由一对数字 $$$(r, c)$$$ ($$$1 \le c \le r$$$) 描述,其中 $$$r$$$ 是层的编号,$$$c$$$ 是层中点的编号。从每个点 $$$(r, c)$$$ 到点 $$$(r+1, c)$$$ 和 $$$(r+1, c+1)$$$ 有两条有向边,但只有其中一条边被激活。如果 $$$r + c$$$ 是偶数,则激活到点 $$$(r+1, c)$$$ 的边缘,否则激活到点 $$$(r+1, c+1)$$$ 的边缘。查看图片以更好地理解。

激活的边缘显示为黑色。未激活的边缘呈灰色。

从点 $$$(r_1, c_1)$$$ 可以到达点 $$$(r_2, c_2)$$$,如果它们之间仅存在来自激活边的路径。例如上图中,有一条从 $$$(1, 1)$$$ 到 $$$(3, 2)$$$ 的路径,但没有从 $$$(2, 1)$$$ 到 $$$(1, 1)$$$ 的路径。

最初,您位于 $$$(1, 1)$$$ 点。对于每一回合,您可以:

- 替换点 $$$(r, c)$$$ 的激活边。也就是说,如果到点 $$$(r+1, c)$$$ 的边被激活,则到点 $$$(r+1, c+1)$$$ 的边被激活,否则,如果到点 $$$(r+1, c+1)$$$ 的边被激活,则到点 $$$(r+1, c)$$$ 的边被激活。此操作使路径成本增加$$$1$$$;
- 沿着激活的边缘从当前点移动到另一个点。此操作不会增加路径的成本。

给你一个无限三角形 $$$(r_1, c_1), (r_2, c_2), \ldots, (r_n, c_n)$$$ 的 $$$n$$$ 点序列。找到从 $$$(1, 1)$$$ 开始的最小成本路径,以任意顺序经过所有 $$$n$$$ 点。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) 是测试用例的数量。然后是 $$$t$$$ 测试用例。

每个测试用例都以包含一个整数的行开头 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) 是要访问的点的数量。

第二行包含$$$n$$$数字$$$r_1, r_2, \ldots, r_n$$$ ($$$1 \le r_i \le 10^9$$$),其中$$$r_i$$$是第$$$i$$$个点所在层的编号。

第三行包含 $$$n$$$ 数字 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \le c_i \le r_i$$$),其中 $$$c_i$$$ 是 $$$r_i$$$ 层中第 $$$i$$$ 点的编号。

保证所有 $$$n$$$ 点都是不同的。

保证至少有一种方法可以遍历所有 $$$n$$$ 点。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出通过相应测试用例中所有点的路径的最小成本。

示例

输入 #1

4
3
1 4 2
1 3 1
2
2 4
2 3
2
1 1000000000
1 1000000000
4
3 10 5 8
2 5 2 4

输出 #1

0
1
999999999
2