E-整数对最小和(100p)

整数对最小和

问题描述

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

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

输入格式

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

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

第三行包含一个正整数 。

输出格式

输出满足要求的最小和。

样例输入

3 1 1 2
3 1 2 3
2

样例输出

4

数据范围

题解

排序

这道题目要求从两个已排序的数组中选择 对元素，使得它们的和最小。解决这个问题的关键在于理解如何高效地找到最小的 对和。

一个直观的思路是：由于两个数组都是升序排列的，最小的和一定来自于两个数组的开头元素。接下来的最小和可能是第一个数组的第二个元素与第二个数组的第一个元素，或者是第一个数组的第一个元素与第二个数组的第二个元素。

基于这个观察，我们可以使用最小堆（优先队列）来解决这个问题：

1. 首先，将所有可能的组合 及其和 放入最小堆中。
2. 每次从堆中取出最小的元素，这就是当前的最小和。
3. 重复步骤 2，直到取出 个元素或堆为空。

参考代码

• 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
    # 从堆中取出前k个最小的和
    for _ in range(min(k, len(min_heap))):
        result += heapq.heappop(min_heap)
    
    return result

# 读取输入
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
k = int(input())

# 调用函数并输出结果
print(min_sum_pairs(arr1[1:], arr2[1:], k))

• C

// 待补充

• Javascript

const readline = require('readline');

const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

let lines = [];

rl.on('line', (line) => {
    lines.push(line);
});

rl.on('close', () => {
    const [size1, ...arr1] = lines[0].split(' ').map(Number);
    const [size2, ...arr2] = lines[1].split(' ').map(Number);
    const k = parseInt(lines[2]);

    console.log(minSumPairs(arr1, arr2, k));
});

function minSumPairs(arr1, arr2, k) {
    // 创建一个数组来存储所有可能的和
    const sums = [];

    // 计算所有可能的和
    for (let num1 of arr1) {
        for (let num2 of arr2) {