【哈希集合】2024D-CPU算力分配

题目描述与示例

本题练习地址：https://www.algomooc.com/problem/P2706

题目描述

现有两组服务器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++

#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];
    }

    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;
}

时空复杂度

时间复杂度：O(N+M)。构建两个哈希集合所需的时间复杂度

空间复杂度：O(N+M)。两个哈希集合所占的空间。