解题思路

• 把两个核心上的进程负载分别记为数组 cpu1[]、cpu2[]。若将两数组排序后完全相同，则称达到“负载平衡”。

• 交换一次的功耗为两被交换任务负载的较小值。

• 关键观察与算法：

  1. 计数判定：将两数组所有数值做频次统计，若某个负载在两数组合并后的出现次数为奇数，则无法分成两半，返回 -1。
  2. 构造需要互换的多重集合：对每个负载 v，目标是让两个数组中 v 的个数都为 total[v]/2。 多出的放入 Aextra（来自 cpu1），缺的放入 Bextra（来自 cpu2，用等价的“多出”表示）。两个集合大小相等。

题目内容

在手机系统中，多核 $CPU$ 普遍应用于每个核心上运行的多个进程。

假设现在有两个 $CPU$ 核心，每个核心上运行了 $n$ 个进程，每个进程都有其各自的负载，记录在整数数组 $cpu1[]$ 和 $cpu2[]$ 中。

为了实现两个核心之间的负载平衡，需要将一些进程进行多次迁核交换，将运行在 $cpu1$ 上的进程与 $cpu2$ 上的进程进行交换，直到两个核心达到负载平衡，每次交换会消耗一定的功耗，功耗的具体计算是两个交换任务的负载的较小值。

这里负载平衡的定义是，两个核心上运行的进程按负载排序后，序列相同，即排序后，两个核心相同下标的负载相同请返回达到负载平衡所需的最小功耗值。如果无法达到负载平衡，请返回 $-1$ 。

输入描述

输入为两行，每一行都是个整数序列 $cpu1[]$ 和 $cpu2[]$ ，分别代表 $cpu1$ 和 $cpu2$ 上的进程负载参数范围:

1.进程个数 $n:1<=n<=10^5$

2.负载范围:$1<=cpu1[i]<=10^8,1<=cpu2[i]<=10^8$

输出描述

输出一个整数，代表达到负载平衡所需的最小功耗值，$-1$ 代表无法完成负载均衡

样例1

输入

4,2,2,4
2,1,1,2

输出

1

说明

$cpu1$ 的下标 $0$ 的元素 $4$ 和 $cpu2$ 下标 $1$ 的元素 $1$ 交换,产生功耗为 $1$ ，此时 $cpu1=[1,2,2,4],cpu2=[2,4,1,2]$ 排序后字列相同

样例2

输入

4,2,2
1,2,1

输出

-1

说明

无法完成负载均衡

开通会员即可查看完整视频题解：1.题目讲解 2.思路分析 3.逐行代码手写