分数: 500 点
问题陈述
给出两个长度序列 N 每个: A = (A_1, A_2, A_3, \dots, A_N) 和 B = (B_1, B_2, B_3, \dots, B_N).
判断是否可以使 A 等于 B 通过重复执行以下操作(可能零次)。如果可能的话,找出执行此操作所需的最少操作数。
- 选择一个整数 i 这样 1 \le i \lt N,并按顺序执行以下操作:
- 交换 A_i 和 A_{i + 1};
- 添加 1 to A_i;
- 减去 1 来自 A_{i + 1}.
约束
- 2 \le N \le 2 \times 10^5
- 0 \le A_i \le 10^9
- 0 \le B_i \le 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 A_3 \dots A_N B_1 B_2 B_3 \dots B_N
输出
如果不可能 A 等于 B,打印 -1.
否则,打印执行此操作所需的最少操作数。
示例输入 1
3 3 1 4 6 2 0
示例输出 1
2
我们可以匹配 A 与 B 分两次操作,如下:
- 首先,执行操作 i = 2,制作 A = (3, 5, 0).
- 接下来,执行操作 i = 1,制作 A = (6, 2, 0).
我们无法通过一次或更少的操作来实现我们的目标。
示例输入 2
3 1 1 1 1 1 2
示例输出 2
-1
这种情况下是无法匹配的 A 与 B.
示例输入 3
5 5 4 1 3 2 5 4 1 3 2
示例输出 3
0
A 可能等于 B 在进行任何操作之前。
示例输入 4
6 8 5 4 7 4 5 10 5 6 7 4 1
示例输出 4
7