Readme

2561.Rearranging-Fruits

如果有些元素在两个数组里都成对出现过，显然我们不会去移动他们。所以我们会用一个hash表，记录每种元素在两个数组里的频次差值。比如Map[3]=2，表示数字3在篮子一里比在篮子二里多出现了2次。反之，Map[4]=-3，表示数字4在篮子一里比在篮子二里少出现了3次。

为了让最后每个元素能在调整之后，出现在两个数组里的频次一样多，那么hash表的value，无论正负，必须都是偶数。否则就无解。

接下来，我们通过这个hash表，根据value/2写出两个数组A与B，可以知道数组A有哪些元素需要换到B里，以及数组B有些元素需要换到A里。显然，这些元素必须的数目都必然相等。我们将它们各自排序后，记做

A: X X X X X X 
B: Y Y Y Y Y Y 

根据规则，每次操作是AB里的元素的对换，代价是min{x,y}。所以会充分利用较小的元素使其成为“代价”来同时换掉较大的数。根据这个规则，假设在上面AB里全局最小的元素是A1，那么它必然会与B的最大元素进行对调。再接下来，假设全局第二小的元素是B1，那么它必然会与A的最大元素进行对调。再记下来，假设全局第三小的元素是B2，那么它必然与A的第二大元素进行对调.... 假设A和B里各自都有n个元素，那么我们进行n次对换的代价，其实就是AB数组里较小的一半（n个）元素。所以我们只需要将AB混合起来，取较小的一半元素之和即可。

但是本题还有另外一种策略。假设在初始状态下，可能全局有一个最小的元素t，但它在两个篮子里出现的频次相等，因此虽然理论上并不需要将t参与交换（即不出现在AB里）。但是我们发现，如果之前方案中交换一次的“代价”大于2t的话，我们不妨就将t作为媒介引入交换。比如，我们想将x与y直接交换，代价是x。但我们可以将步骤改为：将x与t交换，代价是t；再将t与y交换，代价是t。这样总代价就是2t，可能比x还小。

所以最终的答案是，将AB数组混合取最小的n个元素，每个同时再与2t取小，最终累加起来。