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`。