题解

思路推导

对一个数组展开平方并按元素统计贡献，有

$$\sum_{i<j}(a_i+a_j)^2=(n-2)\sum_i a_i^2+\left(\sum_i a_i\right)^2.$$

两个数组中所有元素平方和在交换前后保持不变。因此，令全部 $2n$ 个数之和为 $S$，交换后数组 $a$ 的元素和为 $x$，需要最小化的变量部分只有

$$x^2+(S-x)^2.$$

对每个下标，数组 $a$ 最终恰好选择 $a_i$、$b_i$ 中的一个，所以问题转化为：从每一对数中选择一个，使选择总和尽量接近 $S/2$。

做法

用布尔动态规划维护所有可达总和。初始只有总和 $0$ 可达。依次处理每一对 $(a_i,b_i)$，从此前的每个可达和分别加上 $a_i$ 或 $b_i$，得到新的可达集合。

枚举所有可达的 $x$，取 $x^2+(S-x)^2$ 的最小值，再加上不随交换变化的平方和贡献，即为答案。

正确性证明

每次转移都从当前一对中恰好选择一个数，因此动态规划产生的每个总和都对应一种合法交换方案。反之，任意交换方案在每一对中也恰好为数组 $a$ 选择一个数，按处理顺序执行相同转移后，其总和必然可达。因此可达集合与全部合法方案一一覆盖。

展开式表明，所有方案的平方和项完全相同，方案差异只由 $x^2+(S-x)^2$ 决定。枚举全部可达总和取最小值，得到的就是原问题的全局最优值。

复杂度分析

每组数据中可达总和不超过 $100n$。时间复杂度为 $O(n^2\max(a_i,b_i))$，在本题范围内可写作 $O(n\sum_i\max(a_i,b_i))$；空间复杂度为 $O(\sum_i\max(a_i,b_i))$。