整数对最小和

题目描述

给定两个整数数组array1, array2, 数组元素按升序排列.

假设从array1、array2中分别取出一个元素可构成一对元素, 现在需要取出k对元素, 并对取出的所有元素求和, 计算和的最小值.

注意:

两对元素如果对应于array1, array2中的两个下标均相同, 则视为同一对元素.

输入描述

• 输入两行数组array1, array2, 每行首个数字为数组大小size (0 < size <= 100)
  • 0 < array1[i] <= 1000
  • 0 < array2[i] <= 1000
• 接下来一行为正整数k
  • 0 < k <= array1.size() * array2.size()

输出描述

满足要求的最小和.

示例1

输入:

3 1 1 2
3 1 2 3
2

输出:

4

说明:

• 用例中, 需要取2对元素
• 取第一个数组第0个元素与第二个数组第0个元素组成1对元素[1,1]
• 取第一个数组第1个元素与第二个数组第0个元素组成1对元素[1,1]
• 求和为1+1+1+1=4, 为满足要求的最小和

题解

Python

import sys

def main():
    # 提取 array1
    part1 = input().split()
    size1 = int(part1[0])
    array1 = list(map(int, part1[1:]))
    assert len(array1) == size1
    assert 0 < size1 <= 100

    # 提取 array2
    part2 = input().split()
    size2 = int(part2[0])
    array2 = list(map(int, part2[1:]))
    assert len(array2) == size2
    assert 0 < size2 <= 100

    # 提取整数 k
    k = int(input())

    # Brute force
    # 取得所有的数对
    all_pairs = []
    for num1 in array1:
        for num2 in array2:
            all_pairs.append(num1 + num2)

    # 以升序排序数对
    all_pairs.sort()

    # 取出前 k 对数对的和, 并计算其总和
    ans = sum(all_pairs[:k])
    print(ans)

if __name__ == "__main__":
    main()