思路

• 可行性判定

  • 对每个数值 $v$，合并出现次数 $cnt(v)=cnt_1(v)+cnt_2(v)$。若存在 $cnt(v)$ 为奇数，则无论如何交换都无法均衡，直接返回 $-1$。

• 需要交换的元素集合

  • 对每个数值 $v$，计算差值 $\Delta(v)=cnt_1(v)-cnt_2(v)$。
  • 若 $\Delta(v)>0$，向集合 $A$ 放入 $\Delta(v)/2$ 个 $v$（表示这些值需要从 $bms1$ 移出）。
  • 若 $\Delta(v)<0$，向集合 $B$ 放入 $-\Delta(v)/2$ 个 $v$（表示这些值需要从 $bms2$ 移出）。

题目内容

储能工厂在发货时，一次同时发两个储能集装箱。每个集装箱中均 $M$ 个电芯，用两个数组 $bms1，bms2$ 表示每个集箱中的电芯的电量，为了保证两个集装箱电芯电量的均衡，需要调整两个集装箱中的电芯，使得两个集装箱中的电芯电最完全均衡(根据集装箱中电芯的电量进行排序，如果排序后的结果完全相同，则认为两个集装箱的电芯电量完全均衡)。调整的代价如下：比如交换电芯 $bms1[i]和bms2[j]$，代价为 $min(bms1[i]，bms2[j])$ 。可以多次调整，请返回调整的最小代价。如果无法使得两个集装箱中的电芯电量完全均衡，返回 $-1$

输入描述

第一行是一个整数 $M$ ，表示集装箱内电芯的数量。$1 <= M <= 10^5$。

接下两行是长度均为 $M$ 的整数数组 $bms1$ 和 $bms2$ ，分别代表两个集装箱内电芯的电量

$1 <= bms1[i], bms2[j] <= 10^8$

输出描述

调整的代价(用例保证不会超过 $2^{64}$)

样例1

输入

4
4 5 6 3
5 4 6 2

输出

-1

说明

无论怎么调整，都无法使得两个储能柜的电芯相同

样例2

输入

5
5 2 3 5 6
2 3 3 3 6

输出

3

说明

交换 $bms1[0]$ 和 $bms2[1]$ ，代价为 $3$ ，交换后，$bms1=3$ $2$ $3$ $5$ $6$ ，$bms2=2$ $5$ $3$ $3$ $6$ ，排序后两个集装箱中的电芯电量完全相同，都是 $2$ $3$ $3$ $5$ $6$