返回目录

题目描述

给定两个整数数组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()

输出描述

满足要求的最小和

示例：

题目解析

本题很简单，双重for找出所有整数对，并记录整数对之和，然后排序整数对之和，取出前k个求和，就是题解。

输入的两个数组的长度均不大于100，因此双重for的O(n^2)复杂度也可以接受。

Python算法源码

def main():
    # 读取输入的数组1
    array1_input = input()
    array1 = list(map(int, array1_input.split()))[1:]

    # 读取输入的数组2
    array2_input = input()
    array2 = list(map(int, array2_input.split()))[1:]

    # 读取输入的k值
    k_input = int(input())

    # 创建一个空列表来存储所有可能的元素对的和
    pairs_sum = []

    # 嵌套循环，将array1和array2中的元素两两相加，并将结果存储到pairs_sum中
    for value1 in array1:
        for value2 in array2:
            pairs_sum.append(value1 + value2)

    # 对pairs_sum中的元素进行排序
    pairs_sum.sort()

    # 取出pairs_sum中前k个元素，并使用sum函数计算它们的和
    min_sum = sum(pairs_sum[:k_input])

    # 输出最小和
    print(min_sum)

if __name__ == "__main__":
    main()

C算法源码

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

#define MAX_SIZE 100

int main() {
    int array1[MAX_SIZE], array2[MAX_SIZE];
    int array1_size, array2_size, k;
    int i, j;

    // 读取数组1的大小和元素
    scanf("%d", &array1_size);
    for (i = 0; i < array1_size; ++i) {
        scanf("%d", &array1[i]);
    }

    // 读取数组2的大小和元素
    scanf("%d", &array2_size);
    for (i = 0; i < array2_size; ++i) {
        scanf("%d", &array2[i]);
    }

    // 读取k值
    scanf("%d", &k);

    // 创建一个动态数组来存储所有可能的元素对的和
    int pairs_sum[MAX_SIZE * MAX_SIZE];
    int pairs_index = 0;

    // 嵌套循环，将array1和array2中的元素两两相加，并将结果存储到pairs_sum中
    for (i = 0; i < array1_size; ++i) {
        for (j = 0; j < array2_size; ++j) {
            pairs_sum[pairs_index++] = array1[i] + array2[j];
        }
    }

    // 对pairs_sum中的元素进行排序
    for (i = 0; i < pairs_index - 1; ++i) {
        for (j = 0; j < pairs_index - i - 1; ++j) {
            if (pairs_sum[j] > pairs_sum[j + 1]) {
                int temp = pairs_sum[j];
                pairs_sum[j] = pairs_sum[j + 1];
                pairs_sum[j + 1] = temp;
            }
        }
    }

    // 取出pairs_sum中前k个元素，并计算它们的和
    int min_sum = 0;
    for (i = 0; i < k && i < pairs_index; ++i) {
        min_sum += pairs_sum[i];
    }

    // 输出最小和
    printf("%d\n", min_sum);

    return 0;
}

Java算法源码

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取数组1
        int[] array1 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).skip(1).toArray();

        // 读取数组2
        int[] array2 = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).skip(1).toArray();

        // 读取k值
        int k = Integer.parseInt(scanner.nextLine());

        // 创建一个数组来存储所有可能的元素对的和
        int[] pairsSum = new int[array1.length * array2.length];
        int pairsIndex = 0;

        // 嵌套循环，将array1和array2中的元素两两相加，并将结果存储到pairsSum中
        for (int value1 : array1) {
            for (int value2 : array2) {
                pairsSum[pairsIndex++] = value1 + value2;
            }
        }

        // 对pairsSum中的元素进行排序
        Arrays.sort(pairsSum);

        // 取出pairsSum中前k个元素，并计算它们的和
        int minSum = 0;
        for (int i = 0; i < Math.min(k, pairsSum.length); i++) {
            minSum += pairsSum[i];
        }

        // 输出最小和
        System.out.println(minSum);

        // 关闭scanner
        scanner.close();
    }
}