P17537 [JAG 2026 Summer Camp #1] Rabbit, Rabbit, Rabbit
题目描述
数轴上有 $N$ 只兔子和 $N$ 个饮水点,数轴的正方向向右。第 $i$ 只兔子初始位于坐标 $X_i$,第 $i$ 个饮水点位于坐标 $Y_i$。你可以执行以下操作零次或多次:
- 对这 $N$ 只兔子中的每一只,独立选择让它向左或向右移动距离 $1$。若有 $R$ 只兔子向右移动、$L$ 只兔子向左移动,则本次操作的代价为 $R\times L$。
注意,多只兔子可以同时位于相同的坐标。
你的目标是使这 $N$ 只兔子的坐标与 $N$ 个饮水点的坐标按某种顺序一一对应。求实现这一目标所需的最小总代价。若无法实现,输出 `-1`。
输入格式
输入包含一组或多组测试数据。第一行包含一个整数 $T$($1\le T\le 3\times 10^5$),表示测试数据组数。接下来给出 $T$ 组测试数据,每组格式如下:
```text
N
X_1 X_2 ... X_N
Y_1 Y_2 ... Y_N
```
第一行包含一个整数 $N$($1\le N\le 3\times 10^5$)。
第二行包含 $N$ 个整数 $X_1,X_2,\ldots,X_N$($-10^7\le X_i\le 10^7$)。$X_i$ 表示第 $i$ 只兔子的初始坐标。
第三行包含 $N$ 个整数 $Y_1,Y_2,\ldots,Y_N$($-10^7\le Y_i\le 10^7$)。$Y_i$ 表示第 $i$ 个饮水点的坐标。保证对于任意 $i\ne j$,都有 $Y_i\ne Y_j$。
所有测试数据的 $N$ 之和不超过 $3\times 10^5$。
输出格式
对于每组测试数据,输出实现目标所需的最小总代价。若无法实现,输出 `-1`。