E卷-刷题笔记合集🔗

题目描述

现有两组服务器A和B，每组有多个算力不同的CPU。其中：

• 表示A组第i个CPU的运算能力
• 表示B组第i个CPU的运算能力
• 一组服务器的总算力是各CPU的算力之和

为了让两组服务器的算力相等，允许从每组各选出一个CPU进行一次交换。请找出用于交换的两个CPU的算力值，要求从A组选出的CPU算力尽可能小。

输入格式

输入包含多组测试数据，每组数据包含三行：

第一行输入两个整数 和 ，以空格分隔：

• 表示A组服务器中的CPU数量
• 表示B组服务器中的CPU数量

第二行输入 个整数，表示A组服务器中各个CPU的算力值。

第三行输入 个整数，表示B组服务器中各个CPU的算力值。

输出格式

对于每组测试数据，输出一行，包含两个整数，以空格分隔：

• 第一个整数表示从A组选出的CPU算力
• 第二个整数表示从B组选出的CPU算力

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

样例输入1

2 2
1 1
2 2

样例输出1

1 2

样例解释1

从A组中选出算力为1的CPU，与B组中算力为2的CPU进行交换，使两组服务器的算力都等于3。

样例输入2

3 2
1 2 5
2 4

样例输出2

5 4

数据范围

提示

1. 保证两组服务器的初始总算力不同
2. 保证答案一定存在
3. 注意处理多组测试数据

题解

这是一个数学推导和查找的问题。

解题思路:

1. 数学推导: 设A组总算力为sumA，B组总算力为sumB 交换a和b后两组算力相等，可得: sumA - a + b = sumB - b + a sumA - sumB = 2(a - b) a - b = (sumA - sumB)/2

2. 算法步骤:

   • 计算两组初始总算力sumA和sumB
   • 计算half_diff = (sumA - sumB)/2
   • 遍历A组每个算力值a
   • 计算对应的b = a - half_diff
   • 如果b存在于B组且当前a是最小的可行解，则更新答案

3. 关键点:

   • 使用集合存储B组算力值加速查找
   • 记录并更新A组最小的可行解
   • 处理多组测试数据的输入

参考代码

def read_input():
    """读取输入数据"""
    l1, l2 = map(int, input().split())
    group_a = list(map(int, input().split()))
    group_b = list(map(int, input().split()))
    return l1, l2, group_a, group_b

def calculate_sums(group_a, group_b):
    """计算两组的总算力"""
    sum_a = sum(group_a)
    sum_b = sum(group_b)
    return sum_a, sum_b

def find_min_swap(group_a, group_b, sum_a, sum_b):
    """查找最小交换的CPU算力"""
    half_diff = (sum_a - sum_b) // 2
    set_b = set(group_b)
    
    min_a = float('inf')
    result = None
    
    for a in group_a:
        b = a - half_diff
        if b in set_b and a < min_a:
            min_a = a
            result = (a, b)
    
    return result

def solve():
    while True:
        try:
            l1, l2, group_a, group_b = read_input()
            sum_a, sum