返回目录

题目描述

现有两组服务器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 ≤ 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
说明从A组中选出算力为1的CPU，与B组中算力为2的进行交换，使
两组服务器的算力都等于3。
输入1 2
2
1 3
输出2 3
说明无

题目解析

假设A组服务器算力之和为sumA，B组服务器算力之和为sumB，将A组的a和B组的b交换后，A组算力之和等于B组算力之和，则可得公式如下：

sumA - a + b = sumB - b + a

sumA - sumB = 2 * (a - b)

a - b = (sumA - sumB) / 2

其中 sumA, sumB 是已知的，因此，我们可以遍历A组所有元素a，计算出b= a - (sumA - sumB)/2，看B组中是否存在对应b，若存在，则a b就是题解。

Python算法源码


def process_elements(elements):
   
    pass

# 处理可能存在的多组输入数据
while True:
    try:
        x, y = map(int, input().split())
        arr_x = list(map(int, input().split()))
        set_y = set(map(int, input().split()))

        # 计算两数组元素和的差的一半
        half_diff = (sum(arr_x) - sum(set_y)) // 2

        min_a = float('inf')
        ans = ""
        # 遍历数组 arr_x
        for a in arr_x:
            b = a - half_diff
            if b in set_y:
                if a < min_a:
                    min_a = a
                    ans = f"{a} {b}"

        print(ans)

    except EOFError:
        break

C算法源码

#include <stdio.h>
#include <stdlib.h>

// Helper 结构体
typedef struct {
    // 入参类型和个数
    void (*processElements)(int[]);
} Helper;

// Helper 类的方法
void processElements(int elements[]) {
  
}

int main() {
    // 处理可能存在的多组输入数据
    while (1) {
        int x, y;
        int res = scanf("%d %d", &x, &y);
        if (res != 2) {
            break;
        }

        int sumX = 0;
        int arrX[x];
        int indexX = 0;
        //读取数组arrX
        while (indexX < x) {
            int tempX;
            if (scanf("%d", &tempX) != 1) {
                break;
            }
            sumX += tempX;
            arrX[indexX] = tempX;
            indexX++;
        }

        int sumY = 0;
        int setY[y];
        int indexY = 0;
        // 使用while循环读取数组setY
        while (indexY < y) {
            int tempY;
            if (scanf("%d", &tempY) != 1) {
                break;
            }
            sumY += tempY;
            setY[indexY] = tempY;
            indexY++;
        }

        // 计算两数组元素和的差的一半
        int halfDiff = (sumX - sumY) / 2;

        int minA = __INT_MAX__;
        char ans[15];
        int idx = 0;
        // 使用while循环遍历数组arrX
        while (idx < x) {
            int a = arrX[idx];
            int b = a - halfDiff;

            for (int j = 0; j < y; j++) {
                if (setY[j] == b) {
                    if (a < minA) {
                        minA = a;
                        sprintf(ans, "%d %d", a, b);
                    }
                }
            }
            idx++;
        }

        puts(ans);
    }

    return 0;
}

Java算法源码

import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        // 处理可能存在的多组输入数据
        while (sc.hasNext()) {
            int x = sc.nextInt();
            int y = sc.nextInt();
 
            int sumX = 0;
            int[] arrX = new int[x];
            int indexX = 0;
            // 读取数组arrX
            while (indexX < x) {
                int tempX = sc.nextInt();
                sumX += tempX;
                arrX[indexX] = tempX;
                indexX++;
            }
 
            int sumY = 0;
            HashSet<Integer> setY = new HashSet<>();
            int indexY = 0;
            // 读取HashSet setY
            while (indexY < y) {
                int tempY = sc.nextInt();
                sumY += tempY;
                setY.add(tempY);
                indexY++;
            }
 
            // 计算两数组元素和的差的一半
            int halfDiff = (sumX - sumY) / 2;
 
            int minA = Integer.MAX_VALUE;
            String ans = "";
            int idx = 0;
            // 使用while循环遍历数组arrX
            while (idx < arrX.length) {
                int a = arrX[idx];
                int b = a - halfDiff;
 
                if (setY.contains(b)) {
                    if (a < minA) {
                        minA = a;
                        ans = a + " " + b;
                    }
                }
                idx++;
            }
 
            System.out.println(ans);
        }
    }
  
    static class Helper {
        // 入参类型和个数
        static void processElements(int[] elements) {
            /
        }
    }
}
最后修改：2024 年 03 月 31 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏