2024年华为OD机试真题-整数对最小和
华为OD机试真题-整数对最小和-2024年OD统一考试(D卷)
题目描述:
给定两个整数数组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,为满足要求的最小和
解题思路
又是一道常见的数组题,使用循环和数值处理解题。
JAVA解法:
import java.util.Scanner; import java.util.Arrays; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); String line1 = in.nextLine(); String line2 = in.nextLine(); int k = in.nextInt(); String[] strArray1 = line1.split(" "); String[] strArray2 = line2.split(" "); int n = Integer.parseInt(strArray1[0]); int m = Integer.parseInt(strArray2[0]);; int[] array1 = new int[n]; int[] array2 = new int[m]; for (int i = 0; i < n; i++) { array1[i] = Integer.parseInt(strArray1[i+1]); } for (int i = 0; i < m; i++) { array2[i] = Integer.parseInt(strArray2[i+1]); } int[] res = new int[n*m]; for (int i = 0; i < n*m; i++) { res[i] = Integer.MAX_VALUE; } int l=0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { res[l++] = array1[i]+array2[j]; } } Arrays.sort(res); int sum = 0; for (int i = 0; i < k; i++) { sum+=res[i]; } System.out.println(sum); } }
Python解法:
import sys import heapq lines = [line.strip() for line in sys.stdin.readlines()] array1 = [int(n) for n in lines[0].split()][1:] array2 = [int(n) for n in lines[1].split()][1:] k = int(lines[2]) array = [] total = 0 i, j = 0, 0 heapq.heappush(array, (array1[i] + array2[j], i, j)) visited = set() while k > 0 and array: value, i, j = heapq.heappop(array) if (value, i, j) in visited: continue visited.add((value, i, j)) total += value if i + 1 < len(array1): heapq.heappush(array, (array1[i + 1] + array2[j], i + 1, j)) if j + 1 < len(array2): heapq.heappush(array, (array1[i] + array2[j + 1], i, j + 1)) k -= 1 print(total)
C++解法:
#include <iostream> #include <vector> #include <queue> #include <utility> using namespace std; int minSum(vector<int>& array1, vector<int>& array2, int k) { // 优先队列,最小堆 auto comp = [](const tuple<int, int, int>& a, const tuple<int, int, int>& b) { return get<0>(a) > get<0>(b); }; priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, decltype(comp)> pq(comp); // 初始化堆 for (int i = 0; i < array1.size(); ++i) { pq.push(make_tuple(array1[i] + array2[0], i, 0)); } int sum = 0; while (k-- > 0 && !pq.empty()) { auto [curSum, i, j] = pq.top(); pq.pop(); sum += curSum; if (j + 1 < array2.size()) { pq.push(make_tuple(array1[i] + array2[j+1], i, j+1)); } } return sum;
欢迎交流指正~
#华为od##华为#华为OD机试题库2024年 文章被收录于专栏
2024年OD统一考试(D卷),最新最完整题库。 收录130+道真题,提供解题思路,Java/Python/C++三种答案源码。