33OJ
登录 注册

#P17537. [JAG 2026 Summer Camp #1] Rabbit, Rabbit, Rabbit

[JAG 2026 Summer Camp #1] Rabbit, Rabbit, Rabbit

题目描述

数轴上有 NN 只兔子和 NN 个饮水点,数轴的正方向向右。第 ii 只兔子初始位于坐标 XiX_i,第 ii 个饮水点位于坐标 YiY_i。你可以执行以下操作零次或多次:

  • 对这 NN 只兔子中的每一只,独立选择让它向左或向右移动距离 11。若有 RR 只兔子向右移动、LL 只兔子向左移动,则本次操作的代价为 R×LR\times L。

注意,多只兔子可以同时位于相同的坐标。

你的目标是使这 NN 只兔子的坐标与 NN 个饮水点的坐标按某种顺序一一对应。求实现这一目标所需的最小总代价。若无法实现,输出 -1。

输入格式

输入包含一组或多组测试数据。第一行包含一个整数 TT(1≤T≤3×1051\le T\le 3\times 10^5),表示测试数据组数。接下来给出 TT 组测试数据,每组格式如下:

N
X_1 X_2 ... X_N
Y_1 Y_2 ... Y_N

第一行包含一个整数 NN(1≤N≤3×1051\le N\le 3\times 10^5)。

第二行包含 NN 个整数 X1,X2,…,XNX_1,X_2,\ldots,X_N(−107≤Xi≤107-10^7\le X_i\le 10^7)。XiX_i 表示第 ii 只兔子的初始坐标。

第三行包含 NN 个整数 Y1,Y2,…,YNY_1,Y_2,\ldots,Y_N(−107≤Yi≤107-10^7\le Y_i\le 10^7)。YiY_i 表示第 ii 个饮水点的坐标。保证对于任意 i≠ji\ne j,都有 Yi≠YjY_i\ne Y_j。

所有测试数据的 NN 之和不超过 3×1053\times 10^5。

输出格式

对于每组测试数据,输出实现目标所需的最小总代价。若无法实现,输出 -1。

3
3
2 4 8
-2 6 10
2
0 2
0 1
10
37 -82 14 91 -5 68 -47 22 55 -16
-73 44 19 -88 67 2 95 -31 58 10
6
-1
467