题目描述与示例
题目描述
现有两组服务器A和B，每组有多个算力不同的CPU，其中Ai是A组第i个CPU的运算能力，Bi是B组第i个CPU的运算能力。一组服务器的总算力是各CPU的算力之和。
为了让两组服务器的算力相等，允许从每组各选出一个CPU进行一次交换，求两组服务器中，用于交换的CPU的算力，并且要求从A组服务器中选出的CPU，算力尽可能小。
输入描述
第一行输入为L1和L2，以空格分隔，L1表示A组服务器中的CPU数量，L2表示B组服务器中的CPU数量
第二行输入为A组服务器中各个CPU的算力值，以空格分隔。
第三行输入为B组服务器中各个CPU的算力值，以空格分隔。
1 <= L1 <= 10000
1 <= L2 <= 10000
1 <= A[i] <= 100000
1 <= B[i] <= 100000
输出描述
对于每组测试数据，输出两个整数，以空格分隔，依次表示A组选出的CPU算力、B组选出的CPU算力，要求从A组选出的CPU的算力尽可能小。
补充说明
保证两组服务器的初始总算力不同，答案肯定存在。
示例一
输入
2 2
1 1
2 2
输出
1 2
示例二
输入
3 4
1 2 3
1 2 3 4
输出
1 3
说明
有两种可能的选择，选择A组中的1和B组中的3进行交换，或者选择A组中的2和B组中的4进行交换，但由于要求A组选择的算力要尽可能地小，所以选择前者。
解题思路
注意有两个非常重要的条件：
- 允许从每组各选出一个CPU进行一次交换
- 保证两组服务器的初始总算力不同，答案肯定存在
第一个条件指出，只能在A组和B组中各挑选出1个数据，不用考虑多组交换的情况
第二个条件指出，无需考虑不合规则的情况，必然能够找到一个A[i]和一个B[j]，交换后使得各自的和相等。
假设原A组的和为sumA，原B组的和为sumB，所有CPU的算力总和为sum_total，取出的两个用于交换的元素分别为A[i]和B[j]。
sumA = sum(A)
sumB = sum(B)
sum_total = sumA + sumB
交换后，如果A组的和为sumA_new，B组的和为sumB_new，那么一定存在以下式子成立
sumA_new = sumB_new = sum_total // 2
且sum_total一定是一个偶数。
sumA_new = sum_total // 2
A`组少了一个`A[i]`多了一个`B[j]`，故交换前后的变化量为`sumA_new - sumA = B[j] - A[i]
即如果交换后A组和B组的算力总和相等，存在式子B[j] = sumA_new - sumA + A[i]成立。
因此，我们只需要遍历A组中所有的元素A[i]，然后计算对应的sumA_new - sumA + A[i]，如果该值位于B组中，说明B组中可以找到对应的B[j]。
这个步骤涉及到快速查找，因此很容易想到应该构建哈希集合setB = set(B)。
从示例二可以得知，可以交换的组数不是唯一的。由于题目还要求从A组服务器中选出的CPU，算力尽可能小，因此仅需把所有符合条件的A[i]取最小值即可。
另外，由于A组中可能出现重复元素，重复元素的计算对于本问题而言是无意义的，因此也可以构建setA = set(A)，遍历A组元素时直接遍历setA而非A即可。
代码
Python
# 题目：【哈希集合】2023C-CPU算力分配
# 分值：100
# 作者：闭着眼睛学数理化
# 算法：哈希集合，数学
# 代码看不懂的地方，请直接在群上提问
# 输入A组的长度和B组的长度
nA, nB = map(int, input().split())
# 输入A组的情况
A = list(map(int, input().split()))
# 输入B组的情况
B = list(map(int, input().split()))
# 原A组的总和
sumA = sum(A)
# 原B组的总和
sumB = sum(B)
# 交换后A组的和，为所有元素总和的一半
sumA_new = (sumA + sumB) // 2
# 分别获得A组和B组对应的哈希集合
# setA的作用是去重，setB的作用是快速查找
setA = set(A)
setB = set(B)
# 找到所有满足sumA_new - sumA + Ai位于setB中的Ai的最小值，即为A组中所选的算力ansA
ansA = min(Ai for Ai in setA if (sumA_new - sumA + Ai) in setB)
# 对应地可以计算出ansB
ansB = sumA_new - sumA + ansA
# 输出答案
print(ansA, ansB)
Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int nA = scanner.nextInt();
int nB = scanner.nextInt();
int[] A = new int[nA];
int[] B = new int[nB];
for (int i = 0; i < nA; i++) {
A[i] = scanner.nextInt();
}
for (int i = 0; i < nB; i++) {
B[i] = scanner.nextInt();
}
int sumA = 0, sumB = 0;
for (int num : A) {
sumA += num;
}
for (int num : B) {
sumB += num;
}
int sumANew = (sumA + sumB) / 2;
Set<Integer> setB = new HashSet<>();
for (int num : B) {
setB.add(num);
}
int ansA = Integer.MAX_VALUE;
for (int num : A) {
if (setB.contains(sumANew - sumA + num)) {
ansA = Math.min(ansA, num);
}
}
int ansB = sumANew - sumA + ansA;
System.out.println(ansA + " " + ansB);
}
}
C++
“`C++
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int nA, nB;
cin >> nA >> nB;
vector<int> A(nA), B(nB);
for (int i = 0; i < nA; i++) {
cin >> A[i];
}
for (int i = 0; i < nB; i++) {
cin >> B[i];
}
<pre><code>int sumA = 0, sumB = 0;
for (int num : A) {
sumA += num;
}
for (int num : B) {
sumB += num;
}
int sumANew = (sumA + sumB) / 2;
unordered_set<int> setB(B.begin(), B.end());
int ansA = INT_MAX;
for (int num : A) {
if (setB.count(sumANew – sumA + num)) {
ansA = min(ansA, num);
}
}
int ansB = sumANew – sumA + ansA;
cout << ansA << " " << ansB << endl;
return 0;
</code></pre>
}
“`
时空复杂度
时间复杂度：O(N+M)。构建两个哈希集合所需的时间复杂度
空间复杂度：O(N+M)。两个哈希集合所占的空间。
说明
华为OD机试有三道题⽬，第⼀道和第⼆道属于简单或中等题，分值为 100 分，第三道为中等或困难题，分值为 200分，总分为 400 分。
机试分数越⾼评级越⾼，⼯资也就越⾼。
关于华为 OD 机试更加详细的介绍可以查看这篇⽂章：华为OD机考须知
关于机考题目汇总可以看这篇文章：华为OD机试真题 2023 A+B+C+D卷 + 2024新卷（Python&Java&C++）⽬录汇总（每⽇更新）
