【2025年华为暑期实习(留学生)-7月23日-第三题（300分）- 调整储能集装箱】（题目+思路+Java&C++&Python解析+在线测试)

题目内容

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

输入描述

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

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

1<=bms1[i],bms2[j]<=1081 <= bms1[i], bms2[j] <= 10^81<=bms1[i],bms2[j]<=108

输出描述

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

样例1

输入

44 5 6 35 4 6 2

输出

-1

说明

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

样例2

输入

55 2 3 5 62 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$

题目解析

题面描述

储能工厂在发货时，一次同时发两个储能集装箱，每个集装箱中均有$M$个电芯。用两个数组 bms1、bms2 分别表示每个集装箱中的电芯电量。为了保证两个集装箱电芯电量的均衡，需要通过若干次调整——每次可以交换 bms1[i] 和 bms2[j] 两个电芯，代价为$min(bms1[i],bms2[j])$——使得两个集装箱中的电芯电量完全均衡（即对两个数组分别排序后，排序结果完全相同）。求最小总调整代价；若无法均衡，则返回$-1$。

思路

1. 可行性检测

   • 对所有出现的电量值$v$，统计在两个集装箱中的总出现次数mathrmcnt(v)=mathrmcnt1(v)+mathrmcnt2(v)mathrm{cnt}(v)=mathrm{cnt}_1(v)+mathrm{cnt}_2(v)mathrmcnt(v)=mathrmcnt1​(v)+mathrmcnt2​(v)。
   • 若存在某$v$使得$mathrmcnt(v)$为奇数，则无法两两配对，直接返回$-1$。

2. 计算多余与缺少

   • 对每个$v$，令
     d(v)=mathrmcnt1(v)−mathrmcnt2(v).d(v)=mathrm{cnt}_1(v)-mathrm{cnt}_2(v).d(v)=mathrmcnt1​(v)−mathrmcnt2​(v).

   • 若$d(v)>0$，则集装箱1中多出$tfracd(v)2$个值为$v$的电芯；若$d(v)<0$，则集装箱2中多出$tfrac-d(v)2$个。

   • 将所有多出的电芯电量分别收集到两个列表：

     • $A$：集装箱1中需要“送出”的电芯电量列表，大小为$K$。
     • $B$：集装箱2中需要“送出”的电芯电量列表，大小同样为$K$。

3. 贪心配对与最优代价

   • 全局最小电量记为$g=min(minbms1,minbms2)$。

   • 将$A$、$B$都升序排序。

   • 对于每一对$(A[i],B[i])$，可以通过以下两种方式进行调换：

     1. 直接交换，代价为$min(A[i],B[i])$；
     2. 间接交换（即先将较小电芯与全局最小电芯$g$交换两次），代价为$2g$。

   • 因此每对最优代价为
     $min(min(A[i],B[i]),2g).$

   • 累加所有对的最优代价即为答案。

代码实现

C++

#include using namespace std;using ll = long long;int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int M; cin >> M; vector<ll> bms1(M), bms2(M); for (int i = 0; i < M; i++) cin >> bms1[i]; for (int i = 0; i < M; i++) cin >> bms2[i]; // 统计两个数组中每个电量的出现次数 unordered_map<ll, ll> cnt; ll global_min = LLONG_MAX; for (auto &x : bms1) { cnt[x]++; global_min = min(global_min, x); } for (auto &x : bms2) { cnt[x]++; global_min = min(global_min, x); } // 如果有电量总次数为奇数，不可能均衡 for (auto &p : cnt) { if (p.second % 2 != 0) { cout << -1 << \"\\n\"; return 0; } } // 分别统计每个数组中多余需要交换的电芯 unordered_map<ll, ll> cnt1, cnt2; for (auto &x : bms1) cnt1[x]++; for (auto &x : bms2) cnt2[x]++; vector<ll> A, B; // A: bms1 多余，B: bms2 多余 for (auto &p : cnt) { ll v = p.first; ll d = cnt1[v] - cnt2[v]; if (d > 0) { // 集装箱1多出 d/2 个 v for (ll k = 0; k < d/2; k++) A.push_back(v); } else if (d < 0) { // 集装箱2多出 -d/2 个 v for (ll k = 0; k < (-d)/2; k++) B.push_back(v); } } // 如果待交换列表大小不一致，则出错 if (A.size() != B.size()) { cout << -1 << \"\\n\"; return 0; } int K = A.size(); if (K == 0) { cout << 0 << \"\\n\"; return 0; } // 升序排列，逐对计算最小代价 sort(A.begin(), A.end()); sort(B.begin(), B.end()); ll ans = 0; for (int i = 0; i < K; i++) { // 直接交换代价 或者 通过 global_min 间接交换两次 ans += min(min(A[i], B[i]), 2 * global_min); } cout << ans << \"\\n\"; return 0;}

Python

from collections import Counterdef min_swap_cost(bms1, bms2): M = len(bms1) cnt_total = Counter(bms1) + Counter(bms2) # 可行性检测 for v, c in cnt_total.items(): if c % 2 != 0: return -1 cnt1, cnt2 = Counter(bms1), Counter(bms2) # 全局最小值 g = min(min(bms1), min(bms2)) A = [] B = [] # 构造待交换列表 for v in cnt_total: d = cnt1[v] - cnt2[v] if d > 0: A += [v] * (d // 2) elif d < 0: B += [v] * ((-d) // 2) if len(A) != len(B): return -1 if not A: return 0 A.sort() B.sort() cost = 0 # 贪心配对，取直接交换或通过 g 的最小代价 for x, y in zip(A, B): cost += min(min(x, y), 2 * g) return cost# 示例if __name__ == \"__main__\": M = int(input()) bms1 = list(map(int, input().split())) bms2 = list(map(int, input().split())) print(min_swap_cost(bms1, bms2))

Java

import java.util.*;public class Main { public static long minSwapCost(int[] bms1, int[] bms2) { int M = bms1.length; Map<Integer, Integer> cntTotal = new HashMap<>(); long globalMin = Long.MAX_VALUE; // 统计总次数并找全局最小值 for (int x : bms1) { cntTotal.put(x, cntTotal.getOrDefault(x, 0) + 1); globalMin = Math.min(globalMin, x); } for (int x : bms2) { cntTotal.put(x, cntTotal.getOrDefault(x, 0) + 1); globalMin = Math.min(globalMin, x); } // 奇偶性检测 for (Map.Entry<Integer, Integer> e : cntTotal.entrySet()) { if (e.getValue() % 2 != 0) { return -1; } } // 统计各自数组次数 Map<Integer, Integer> cnt1 = new HashMap<>(); Map<Integer, Integer> cnt2 = new HashMap<>(); for (int x : bms1) cnt1.put(x, cnt1.getOrDefault(x, 0) + 1); for (int x : bms2) cnt2.put(x, cnt2.getOrDefault(x, 0) + 1); List<Integer> A = new ArrayList<>(); List<Integer> B = new ArrayList<>(); // 构造多余元素列表 for (int v : cntTotal.keySet()) { int d = cnt1.getOrDefault(v, 0) - cnt2.getOrDefault(v, 0); if (d > 0) { for (int i = 0; i < d/2; i++) A.add(v); } else if (d < 0) { for (int i = 0; i < (-d)/2; i++) B.add(v); } } if (A.size() != B.size()) return -1; if (A.isEmpty()) return 0; Collections.sort(A); Collections.sort(B); long ans = 0; // 贪心配对 for (int i = 0; i < A.size(); i++) { long x = A.get(i), y = B.get(i); ans += Math.min(Math.min(x, y), 2 * globalMin); } return ans; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int M = sc.nextInt(); int[] bms1 = new int[M], bms2 = new int[M]; for (int i = 0; i < M; i++) bms1[i] = sc.nextInt(); for (int i = 0; i < M; i++) bms2[i] = sc.nextInt(); System.out.println(minSwapCost(bms1, bms2)); }}