[R46F]环操作 - 代码源竞赛平台

时空限制

1S/256M

题目描述

出题人想象力枯竭了，所以本题没有神秘题面。

给定两个长度为 $n$ 的整数序列 $a_0, a_1, \dots, a_{n-1}$ 和 $b_0, b_1, \dots, b_{n-1}$，序列是循环的（即下标模 $n$）。

你可以执行以下操作任意多次（包括零次）：

• 选择一个下标 $i$（$0 \le i \le n-1$）和一个整数 $x$（可以为负）。
• 将 $a_i$ 增加 $x$，将 $a_{(i+1)\bmod n}$ 增加 $-2x$，将 $a_{(i+2)\bmod n}$ 增加 $x$。

每次操作的代价为 $|x|$，即 $x$ 的绝对值。
你的目标是经过一系列操作后，使得对于所有 $i$ 都有 $a_i = b_i$。
你需要计算达成目标的最小总代价，如果无法达成则输出 $-1$。

格式

输入格式

本题输入包含多组测试数据。

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

对于每组测试数据：

• 第一行包含一个整数 $n$，表示序列的长度。
• 第二行包含 $n$ 个整数 $a_0\dots a_{n-1}$。
• 第三行包含 $n$ 个整数 $b_0\dots b_{n-1}$。

本题读入量较大，请选择较快速的方式读入。

输出格式

对于每组测试数据，输出一行一个整数，表示最小总代价或无法达成。

样例

样例输入 #1

5
1
0
0
2
1 0
0 1
3
1 2 3
2 3 4
4
0 0 0 0
1 -2 1 0
5
0 0 0 0 0
1 -1 -1 1 0

样例输出 #1

0
-1
-1
1
2

数据规模

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

子任务编号	分数	$n\le$	$\sum n\le$	依赖子任务	特殊性质
$1$	$20$	$8$			有
$2$	$20$	$100$	$1000$	$1$	无
$3$	$60$	$10^5$	$10^6$	$1,2$

特殊性质：设第 $i$ 个位置的操作值的代价和为 $x_i$，保证输入有解，且存在一组解满足 $1\le x_i\le 8$。

对于 $100\%$ 的数据，保证 $1\le T\le 10000$，$1\le n\le 10^5$，$1\le \sum n\le 10^6$，$-5000\le a_i,b_i\le 5000$。