[R73D]计数器 - 代码源竞赛平台

时空限制

2S/512M

题目描述

有 $n$ 个带编号的计数器，编号依次为 $1,2,\ldots,n$，当前显示的正整数分别为 $x_1,x_2,\ldots,x_n$。

一次操作按以下方式进行：

1. 选择一个满足 $x_i=\min(x_1,x_2,\ldots,x_n)$ 的计数器 $i$。若有多个计数器满足条件，可以任选一个；
2. 记操作前 $M=\max(x_1,x_2,\ldots,x_n)$，令 $x_i:=x_i+M$，其余计数器的值不变。

给定每个计数器的初始值 $a_i$ 和目标值 $b_i$。初始时，令 $x_i=a_i$。你可以进行零次或多次操作。

求使得对于所有 $1\le i\le n$，均有 $x_i=b_i$ 所需的最少操作次数。若无法达到目标状态，输出 $-1$。

格式

输入格式

本题有多组测试数据。

第一行包含一个正整数 $T$，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个正整数 $n$，表示计数器的数量；
• 第二行包含 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示各计数器的初始值；
• 第三行包含 $n$ 个正整数 $b_1,b_2,\ldots,b_n$，表示各计数器的目标值。

输出格式

对于每组测试数据，输出一行一个整数，表示达到目标状态所需的最少操作次数。若无法达到目标状态，输出 $-1$。

样例

样例输入 #1

5
4
1 1 1 1
2 4 3 5
5
2 3 5 7 11
13 3 5 7 11
4
1 1 1 1
2 2 1 1
2
5 8
5 8
3
1 2 3
4 6 9

样例输出 #1

4
1
-1
0
3

样例解释 #1

对于第一组测试数据，可以按如下方式操作：

$$(1,1,1,1)\to(2,1,1,1)\to(2,1,3,1)\to(2,4,3,1)\to(2,4,3,5)。$$

每次操作只会改变一个计数器的值，而四个计数器的值均发生了改变，因此最少需要进行 $4$ 次操作。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	特殊性质
$1$	$50$	特殊性质 A
$2$		无

特殊性质 A：$a_1,a_2,\ldots,a_n$ 两两不同。

对于 $100\%$ 的数据，满足 $1\le T\le 10^4$，$2\le n\le 2\times 10^5$，$1\le a_i,b_i\le 10^9$，且所有测试数据中 $n$ 的总和不超过 $2\times 10^5$。