华为OD机试-整数对最小和

题目描述

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

输出描述

满足要求的最小和

思路

组合出所有可能的整数对，并求和
对所有求和结果升序排序
对最小的k个和进行求和

Java实现

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    try (Scanner scanner = new Scanner(System.in)) {
      int[] arr1 = parseArr(scanner.nextLine());
      int[] arr2 = parseArr(scanner.nextLine());
      int k = scanner.nextInt();
      fn(arr1, arr2, k);
    }
  }

  private static void fn(int[] arr1, int[] arr2, int k) {
    int initialCapacity = arr1.length * arr1.length;
    List<Integer> sums = new ArrayList<>(initialCapacity);
    for (int x : arr1) {
      for (int y : arr2) {
        sums.add(x + y);
      }
    }
    sums.sort(Integer::compareTo);
    int res = 0;
    for (int i = 0; i < k; i++) {
      res += sums.get(i);
    }
    System.out.println(res);
  }

  private static int[] parseArr(String line) {
    String[] split = line.split(" ");
    int[] arr = new int[split.length];
    for (int i = 0; i < arr.length; i++) {
      arr[i] = Integer.parseInt(split[i]);
    }
    return arr;
  }
}

Python实现

# 读取输入
line1, line2, k = input(), input(), int(input())

# 函数用于将字符串解析为列表
def parse_array(line):
    split = line.split()
    return [int(split[s]) for s in range(1, len(split))]


# sums用于保存所有整数对的和，res用于最终保存结果
sums, res = [], 0
# 组合出所有可能的整数对，并求和
for x in parse_array(line1):
    for y in parse_array(line2):
        sums.append(x + y)
# 升序排序
sums.sort()
# 前k个求和
for i in range(k):
    res += sums[i]

print(res)