分数: 700 点
问题陈述
没有两个相邻元素相同的整数序列称为 好的序列.
给你两个长度合适的序列 N: A=(A_1,A_2,\dots,A_N) 和 B=(B_1,B_2,\dots,B_N)。的每个元素 A 和 B 介于 0 和 M-1,包括在内。
您可以对 A 任意次数,可能为零:
- 选择一个整数 i 之间 1 和 N,包括在内,并执行以下操作之一:
- 设置 A_i \leftarrow (A_i + 1) \bmod M.
- 设置 A_i \leftarrow (A_i - 1) \bmod M。在这里, (-1) \bmod M = M - 1.
但是,您无法执行使 A 不再是一个好的序列。
确定是否可以使 A 等于 B,如果可能的话,找到执行此操作所需的最少操作数。
约束
- 2 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 10^6
- 0\leq A_i,B_i< M(1\leq i\leq N)
- A_i\ne A_{i+1}(1\leq i\leq N-1)
- B_i\ne B_{i+1}(1\leq i\leq N-1)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M A_1 A_2 \dots A_N B_1 B_2 \dots B_N
输出
如果目标无法实现,则打印 -1.
否则,以整数形式打印所需的最小操作数。
示例输入 1
3 9 2 0 1 4 8 1
示例输出 1
3
您可以通过以下三个操作来实现目标:
- 设置 A_1 \leftarrow (A_1 + 1) \bmod M。现在 A = (3, 0, 1).
- 设置 A_2 \leftarrow (A_2 - 1) \bmod M。现在 A = (3, 8, 1).
- 设置 A_1 \leftarrow (A_1 + 1) \bmod M。现在 A = (4, 8, 1).
不可能通过两次或更少的操作来实现目标,所以答案是3。
例如,您不能设置 A_2 \leftarrow (A_2 + 1) \bmod M 在第一个操作中,因为它会使 A = (2, 1, 1),这不是一个好的序列。
示例输入 2
3 9 1 8 2 1 8 2
示例输出 2
0
A 和 B 可能从一开始就相等。
示例输入 3
24 182 128 115 133 52 166 92 164 119 143 99 54 162 86 2 59 166 24 78 81 5 109 67 172 99 136 103 136 28 16 52 2 85 134 64 123 74 64 28 85 161 19 74 14 110 125 104 180 75
示例输出 3
811