OD C卷 - CPU算力分配

CPU算力分配

• 两组服务器A、B, 每组有多个算力不同的CPU；
• 为了让两组服务器的算力和相等，允许两组各选出一个CPU进行一次交换；
• 求两组中用于交换的CPU算力，从A中选出的算力尽可能小；

输入描述：
第一行 输入L1, L2 表示A、B组的CPU数量；
第二行输入A组服务器中的CPU算力；
第三行输入B组服务器的CPU算力;
输出描述：
A、B组选出的CPU算力，以空格分开; 保证初始两组算力和不同，且答案肯定存在；

示例1
输入：
2 2
1 1
2 2
输出：
1 2

示例2
输入：
2 2
1 2
2 3
输出：
1 2

示例3
输入：
3 2
1 2 5
2 4
输出：
5 4

思路：

• A数组升序排序，B数组升序排序；
• 遍历A数组的每个元素$A[i]$，根据公式求对应的目标值tgt，是否在B数组中；
  • 交换一次后，存在公式 $\sum A-A_i+B_i=\sum B-B_i+A_i$
  • 代码形式 tgt = A[i] - (sum(A) - sum(B)) // 2
  • 如果tgt 在B数组中存在，则结束对A的循环；
  • 时间复杂度 O(nlogn)

a_len, b_len = list(map(int, input().strip().split()))a_arr = list(map(int, input().strip().split()))
a_sum = sum(a_arr)
b_arr = list(map(int, input().strip().split()))
b_sum = sum(b_arr)a_arr.sort()
b_arr.sort()
i = 0
while i < a_len:  # O(n) + O(nlogn)target = a_arr[i] - (a_sum - b_sum) // 2if target in b_arr:print(str(a_arr[i]) + " " + str(target))breaki += 1