刷题笔记合集🔗

CPU算力分配

问题描述

小基 正在管理两组服务器 A 和 B，每组有多个算力不同的 CPU，其中 是 A 组第 个 CPU 的运算能力， 是 B 组第 个 CPU 的运算能力。

一组服务器的总算力是各 CPU 的算力之和。

为了让两组服务器的算力相等，允许从每组各选出一个 CPU 进行一次交换。

请求出两组服务器中，用于交换的 CPU 的算力，并且要求从 A 组服务器中选出的 CPU，算力尽可能小。

输入格式

第一行输入为 和 ，以空格分隔， 表示 A 组服务器中的 CPU 数量， 表示 B 组服务器中的 CPU 数量。

第二行输入为 A 组服务器中各个 CPU 的算力值，以空格分隔。

第三行输入为 B 组服务器中各个 CPU 的算力值，以空格分隔。

输出格式

对于每组测试数据，输出两个整数，以空格分隔，依次表示 A 组选出的 CPU 算力，B 组选出的 CPU 算力。

要求从 A 组选出的 CPU 的算力尽可能小。

样例输入

2 2
1 1
2 2

2 2
1 2
2 3

1 2
2
1 3

3 2
1 2 5
2 4

样例输出

1 2

1 2

2 3

5 4

数据范围

题解

这道题的关键是理解如何找到合适的 CPU 对进行交换，使得两组服务器的算力相等。

假设 A 组服务器的总算力为 sumA，B 组服务器的总算力为 sumB。交换之后，A 组的算力变为 sumA - a + b，B 组的算力变为 sumB - b + a，其中 a 是从 A 组选出的 CPU 算力，b 是从 B 组选出的 CPU 算力。

要使两组算力相等，需要满足： sumA - a + b = sumB - b + a

化简得： sumA - sumB = 2 * (a - b) a - b = (sumA - sumB) / 2

这意味着，对于给定的 sumA 和 sumB，我们可以确定 a 和 b 之间的差值。因此，对于 A 组中的每个 CPU 算力 a，我们可以计算出需要的 B 组 CPU 算力 b = a - (sumA - sumB) / 2。

解题步骤：

1. 计算 A 组和 B 组的总算力 sumA 和 sumB
2. 计算半差值 half_diff = (sumA - sumB) / 2
3. 将 B 组的所有 CPU 算力存入集合（用于快速查找）
4. 遍历 A 组的每个 CPU 算力 a，计算对应需要的 b = a - half_diff
5. 检查 b 是否在 B 组中存在，如果存在，则找到了一个有效的交换对
6. 在所有有效的交换对中，选择 a 最小的那一对作为答案

这种方法的时间复杂度为 O(L1 + L2)，空间复杂度为 O(L2)，其中 L1 和 L2 分别是 A 组和 B 组的 CPU 数量。

题目保证答案一定存在，所以我们不需要考虑找不到有效交换对的情况。

参考代码

• Python

import sys
input = lambda:sys.stdin.readline().strip()

# 解决一组测试数据
def solve():
    # 读取输入
    l1, l2 = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    # 计算总算力
    sum_a = sum(A)
    sum_b = sum(B)
    
    # 计算半差值
    half_diff = (sum_a - sum_b) // 2
    
    # 将B组CPU算力存入集合，用于快速查找
    set_b = set(B)
    
    # 记录最小的a值
    min_a = float('inf')
    result = ""
    
    # 遍历A组每个CPU
    for a in A:
        # 计算需要的B组CPU算力
        b = a - half_diff
        
        # 检查b是否在B组中存在
        if b in set_b:
            # 更新最小的a
            if a < min_a:
                min_a =