思路

可行性判定
- 对每个数值 $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$ 移出）。

P3655.第3题-调整储能集装箱

1000ms

Tried: 609

Accepted: 106

Difficulty: 6

所属公司 : 华为

算法与标签>贪心算法

题目内容

储能工厂在发货时，一次同时发两个储能集装箱。每个集装箱中均 $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

输出

说明

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

输入

预期输出（选填）

思路

P3655.第3题-调整储能集装箱

题目内容

输入描述

输出描述

样例1

样例2

Status

Development

Support

About