最新华为OD机试真题-最小配对和(100分)

大家好这里是清隆学长 ，一枚热爱算法的程序员

✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解

感谢大家的订阅➕ 和 喜欢

在线评测链接

=> 最小配对和(100分) <=

评测功能需要 =>订阅专栏<= 后联系清隆解锁～

OJ题目截图

最小配对和

问题描述

给定两个按升序排列的整数数组 和 。从 和 中分别取出一个元素构成一对元素，现在需要取出 对元素并对取出的所有元素求和，计算和的最小值。

注意：两对元素如果对应于 、 中的两个下标均相同，则视为同一对元素。

输入格式

第一行包含 和 ，共 个整数，表示数组 的大小和元素 。

第二行包含 和 ，共 个整数，表示数组 的大小和元素 。

第三行包含一个正整数 。

输出格式

输出满足要求的最小和。

样例输入

3 1 1 2
3 1 2 3
2

样例输出

4

数据范围

题解

这道题要求从两个排序数组中选择 对元素，使得其和最小。我们可以利用最小堆来解决这个问题。先将所有可能的组合放入堆中，然后从堆中取出前 个组合的和即为答案。需要判断堆的大小和 的大小，取最小的值进行计算。

参考代码

• Python

import heapq

def min_sum_pairs(arr1, arr2, k):
    min_heap = []
    for num1 in arr1:
        for num2 in arr2:
            heapq.heappush(min_heap, num1 + num2)

    result = 0
    for _ in range(min(k, len(min_heap))):
        result += heapq.heappop(min_heap)
    return result

if __name__ == "__main__":
    arr1 = list(map(int, input().split()))
    arr2 = list(map(int, input().split()))
    k = int(input())
    print(min_sum_pairs(arr1[1:], arr2[1:], k))

• Java

import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int size1 = in.nextInt();
        int[] array1 = new int[size1];
        for (int i = 0; i < size1; i++) {
            array1[i] = in.nextInt();
        }

        int size2 = in.nextInt();
        int[] array2 = new int[size2];
        for (int i = 0; i < size2; i++) {
            array2[i] = in.nextInt();
        }

        int k = in.nextInt();

        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num1 : array1) {
            for (int num2 : array2) {
                minHeap.add(num1 + num2);
            }
        }

        int result = 0;
      	int sz = minHeap.size();
        for (int i = 0; i < Math.min(k, sz); i++) {
            result += minHeap.poll();
        }

        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
int main() {
    int size1, size2, k;
    cin >> size1;
    vector<int> array1(size1);
    for (int i = 0; i < size1; i++) {
        cin >> array1[i];
    }

    cin >> size2;
    vector<int> array2(size2);
    for (int i = 0; i < size2; i++) {
        cin >> array2[i];
    }

    cin >> k;

    priority_queue<int, vector<int>, greater<int>> minHeap;
    for (int num1 : array1) {
        for (int num2 : array2) {
            minHeap.push(num1 + num2);
        }
    }

    int result = 0;
  	int sz = minHeap.size();
    for (int i = 0; i < min(k, sz); i++) {
        result += minHeap.top();
        minHeap.pop();
    }

    cout << result << endl;
    return 0;
}