← 返回题目列表

Codeforces · 2237/B

B. 惹恼鬼

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

幽灵 Ja 正在玩橡皮鸭。他将 $$$n$$$ 堆橡皮鸭排成一排,其中第 $$$i$$$ 堆包含 $$$a_i$$$ 鸭子。嘎嘎鸭给了贾一个 严格增加 序列 $$$b_1,b_2,\ldots,b_n$$$ 并命令他使桩 $$$a_1,a_2,\ldots,a_n$$$ 恰好变成这个序列。

Ja 分以下两个阶段执行该过程:

  1. Ja 可以向每堆添加任意数量的鸭子。

    正式地,对于每堆 $$$i$$$,他选择一个非负整数 $$$x_i$$$ 并将 $$$a_i$$$ 替换为 $$$a_i+x_i$$$。

  2. Ja 可以重复交换相邻的两堆。

    正式地,他可以执行以下操作任意次数,可能为零:选择一个索引$$$i$$$,使得$$$1\le i\le n-1$$$,并交换$$$a_i$$$和$$$a_{i+1}$$$的值。

一个进程被调用 有效 如果两个阶段结束后,堆大小的序列恰好是$$$b_1,b_2,\ldots,b_n$$$。

找出在 第二阶段 其中 有效 进程。如果没有 有效 进程,输出$$$-1$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 2000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le 2000$$$) — 橡皮鸭的堆数。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — 每堆橡皮鸭的初始数量。

第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1\le b_1 \lt b_2 \lt \cdots \lt b_n\le 10^9$$$) — 每堆橡皮鸭的最终数量。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2000$$$。

输出

对于每个测试用例,输出一个整数 - 在测试用例中执行的最小可能操作数 第二阶段 其中 有效 进程。如果没有 有效 进程,输出$$$-1$$$。

示例

输入
复制

10
3
1 2 2
1 3 5
3
2 2 1
1 2 3
2
5 1
2 4
6
6 5 4 3 2 1
1 2 3 4 5 6
7
4 7 1 6 2 5 3
1 2 3 4 5 6 7
2
2 1
2 3
4
3 2 2 1
1 2 3 4
4
4 3 2 1
1 3 4 5
5
1 5 4 3 2
2 3 4 5 6
5
10 3 8 6 9
3 6 8 9 10

输出
复制

0
2
-1
15
12
0
4
4
3
5

注意

在第一个测试用例中,Ja 只需要第一阶段。他可以设置$$$x_1=0,x_2=1,x_3=3$$$,这样一堆堆就变成了$$$1,3,5$$$。不需要交换,所以答案是$$$0$$$。

在第二个测试用例中,Ja 需要两个阶段。他可以设置$$$x_1=0,x_2=1,x_3=0$$$,这样堆就变成了$$$2,3,1$$$。然后他可以执行两次交换: $$[2,3,1]\to [2,1,3]\to [1,2,3].$$ 带有 $$$1$$$ 鸭子的堆必须从第三个位置移动到第一个位置,因此至少需要两次交换。因此答案是$$$2$$$。

在第三个测试用例中,这是不可能的。第一堆最初包含 $$$5$$$ 鸭子,但目标序列中的每个数字最多为 $$$4$$$。由于 Ja 只能添加鸭子而不能删除它们,因此该堆不能等于目标序列中的任何数字。因此答案是$$$-1$$$。

在第四个测试用例中,不需要添加鸭子。 Ja 只需要将这些堆重新排序为递增的顺序。相邻交换的最小数量为$$$15$$$。

在第五个测试用例中,不需要添加鸭子。同样,Ja 只需要将这些堆重新排序为递增的顺序。相邻交换的最小数量为 $$$12$$$。