CF1637D Yet Another Minimization Problem

给定两个长度为 $n$ 的数组 $a$ 和 $b$。 你可以进行如下操作任意次（也可以一次都不做）：选择一个下标 $i$（$1 \leq i \leq n$），交换 $a_i$ 和 $b_i$ 的值。 我们定义数组 $a$ 的代价为 $\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (a_i + a_j)^2$。同理，数组 $b$ 的代价为 $\sum_{i=1}^{n} \sum_{j=i + 1}^{n} (b_i + b_j)^2$。 你的任务是通过若干次操作，使得两个数组的总代价最小。

输入包含若干组测试数据。第一行包含一个整数 $t$（$1 \leq t \leq 40$），表示测试数据组数。接下来是每组测试数据的描述。 每组测试数据的第一行包含一个整数 $n$（$1 \leq n \leq 100$），表示数组的长度。 第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \leq a_i \leq 100$），表示第一个数组的元素。 第三行包含 $n$ 个整数 $b_1, b_2, \ldots, b_n$（$1 \leq b_i \leq 100$），表示第二个数组的元素。 保证所有测试数据中 $n$ 的总和不超过 $100$。

对于每组测试数据，输出一个整数，表示两个数组的最小总代价。

在第二组测试数据中，一种最优方案是经过若干次操作后 $a = [2, 6, 4, 6]$，$b = [3, 7, 6, 1]$。 数组 $a$ 的代价为 $(2 + 6)^2 + (2 + 4)^2 + (2 + 6)^2 + (6 + 4)^2 + (6 + 6)^2 + (4 + 6)^2 = 508$。 数组 $b$ 的代价为 $(3 + 7)^2 + (3 + 6)^2 + (3 + 1)^2 + (7 + 6)^2 + (7 + 1)^2 + (6 + 1)^2 = 479$。 两个数组的总代价为 $508 + 479 = 987$。 由 ChatGPT 4.1 翻译