华为OD机试真题-CPU算力分配_cpu算力分配华为

算法-CPU算力分配

题目描述

现有两组服务器A和B，每组有多个算力不同的CPU，其中A[i]是A组第i个CPU的运算能力，B[i]是B组第i个CPU的运算能力。一组服务器的总算力是各CPU的算力之和。为了让两组服务器的算力相等，允许从每组各选出一个CPU进行一次交换，求两组服务器中，用于交换的CPU的算力，并且要求从A组服务器中选出的CPU，算力尽可能小。

输入描述:

第一行输入为L1和L2，以空格分隔，L1表示A组服务器中的CPU数量，L2表示B组服务器中的CPU数量。第二行输入为A组服务器中各个CPU的算力值，以空格分隔。第三行输入为B组服务器中各个CPU的算力值，以空格分隔。1<=L1<=100001<=L2<=100001 <=A[i]<=1000001 <=B[i]<=100000

输出描述:

对于每组测试数据，输出两个整数，以空格分隔，依次表示A组选出的CPU算力、B组选出的CPU算力。要求从A组选出的CPU的算力尽可能小。

备注: 保证两组服务器的初始总算力不同。答案肯定存在。

 Java实现

import java.util.*;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int L1 = scanner.nextInt(); // A组服务器中的CPU数量
        int L2 = scanner.nextInt(); // B组服务器中的CPU数量
        int[] A = new int[L1]; // A组服务器中各个CPU的算力值
        int[] B = new int[L2]; // B组服务器中各个CPU的算力值
 
        // 读取A组服务器中各个CPU的算力值
        for (int i = 0; i < L1; i++) {
            A[i] = scanner.nextInt();
        }
 
        // 读取B组服务器中各个CPU的算力值
        for (int i = 0; i < L2; i++) {
            B[i] = scanner.nextInt();
        }
 
        // 计算 A 组和 B 组的总算力
        int sumA = Arrays.stream(A).sum(); // 计算A组服务器的总算力
        int sumB = Arrays.stream(B).sum(); // 计算B组服务器的总算力
 
        // 记录 A 组中每个算力的位置，使用Map来记录每个算力值对应的索引位置
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < L1; i++) {
            map.put(A[i], i); // 将算力值及其索引位置加入到map中
        }
 
        // 遍历 B 组的算力，查看是否存在一个算力能够使得两组服务器的算力相等
        for (int i = 0; i < L2; i++) {
            int target = (sumA - sumB + 2 * B[i]) / 2; // 计算目标算力值
            if (map.containsKey(target)) { // 判断是否存在目标算力值在A组中
                System.out.println(target + " " + B[i]); // 输出满足条件的一对CPU的算力值
                return; // 结束程序，因为题目要求只需要找到一对满足条件的CPU
            }
        }
    }
}

解题思路

通过计算两组服务器的总算力，并将A组服务器中每个CPU的算力值及其位置存储在一个HashMap中。然后遍历B组服务器的CPU算力值，计算出一个目标算力值，使得将该算力值从B组换到A组后，两组服务器的总算力相等。

具体步骤如下：

1. 读取输入，包括A组和B组服务器中CPU的数量以及它们各自的算力值。
2. 计算A组和B组的总算力分别为sumA和sumB。
3. 创建一个HashMap(map)，用于记录A组中每个CPU的算力值和对应的索引位置。
4. 遍历B组的CPU算力值，对于每个B组的CPU算力值，计算出需要从B组换到A组的目标算力值target，使得两组服务器的总算力相等。
5. 检查目标算力值是否在A组中，如果在，则输出该目标算力值和当前B组的CPU算力值，即找到满足条件的一对CPU。
6. 如果没有找到满足条件的一对CPU，程序结束。

通过这种方式，代码实现了在给定两组服务器的CPU算力值情况下，找到一对CPU使得交换后两组服务器的总算力相等的功能。

 注释：

有关

int target = (sumA - sumB + 2 * B[i]) / 2;

代码的解释：

这部分代码是用来遍历B组的算力，并查找是否存在一个算力能够使得A组和B组的总算力相等。

在循环中，我们首先计算目标算力值target。根据题目要求，我们需要找到一个算力值x，使得 (sumA - sumB + 2 * x) / 2 等于 target。这个公式的推导如下：

(sumA - sumB) + 2 * x = 2 * target
2 * x = 2 * target - (sumA - sumB)
x = target - (sumA - sumB) / 2

因此，我们计算出了目标算力值target。

接下来，我们通过判断map是否包含这个target，来确定是否存在这样的算力值在A组中。如果存在，则说明我们找到了一对CPU，使得交换后两组服务器的总算力相等。我们将结果输出，并使用return语句结束程序。这是因为题目要求只需要找到一对满足条件的CPU即可。