最新华为OD机试真题-最小配对和(100分)
🍭 大家好这里是清隆学长 ,一枚热爱算法的程序员
✨ 本系列打算持续跟新华为OD-C/D卷的三语言AC题解
👏 感谢大家的订阅➕ 和 喜欢💗
📎在线评测链接
🌍 评测功能需要 =>订阅专栏<= 后联系清隆解锁~
🍓OJ题目截图
💊 最小配对和
问题描述
给定两个按升序排列的整数数组 和
。从
和
中分别取出一个元素构成一对元素,现在需要取出
对元素并对取出的所有元素求和,计算和的最小值。
注意:两对元素如果对应于 、
中的两个下标均相同,则视为同一对元素。
输入格式
第一行包含 和
,共
个整数,表示数组
的大小和元素
。
第二行包含 和
,共
个整数,表示数组
的大小和元素
。
第三行包含一个正整数
。
输出格式
输出满足要求的最小和。
样例输入
3 1 1 2
3 1 2 3
2
样例输出
4
数据范围
题解
这道题要求从两个排序数组中选择 对元素,使得其和最小。我们可以利用最小堆来解决这个问题。先将所有可能的组合放入堆中,然后从堆中取出前
个组合的和即为答案。需要判断堆的大小和
的大小,取最小的值进行计算。
参考代码
- 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
for _ in range(min(k, len(min_heap))):
result += heapq.heappop(min_heap)
return result
if __name__ == "__main__":
arr1 = list(map(int, input().split()))
arr2 = list(map(int, input().split()))
k = int(input())
print(min_sum_pairs(arr1[1:], arr2[1:], k))
- Java
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int size1 = in.nextInt();
int[] array1 = new int[size1];
for (int i = 0; i < size1; i++) {
array1[i] = in.nextInt();
}
int size2 = in.nextInt();
int[] array2 = new int[size2];
for (int i = 0; i < size2; i++) {
array2[i] = in.nextInt();
}
int k = in.nextInt();
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num1 : array1) {
for (int num2 : array2) {
minHeap.add(num1 + num2);
}
}
int result = 0;
int sz = minHeap.size();
for (int i = 0; i < Math.min(k, sz); i++) {
result += minHeap.poll();
}
System.out.println(result);
}
}
- Cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int main() {
int size1, size2, k;
cin >> size1;
vector<int> array1(size1);
for (int i = 0; i < size1; i++) {
cin >> array1[i];
}
cin >> size2;
vector<int> array2(size2);
for (int i = 0; i < size2; i++) {
cin >> array2[i];
}
cin >> k;
priority_queue<int, vector<int>, greater<int>> minHeap;
for (int num1 : array1) {
for (int num2 : array2) {
minHeap.push(num1 + num2);
}
}
int result = 0;
int sz = minHeap.size();
for (int i = 0; i < min(k, sz); i++) {
result += minHeap.top();
minHeap.pop();
}
cout << result << endl;
return 0;
}
#OD##华为OD##华为##秋招##笔试#最新华为OD机试-C&D卷 文章被收录于专栏
本专栏给大家提供了华为2024最新华为OD-C/D卷的题目汇总和(Java/Cpp/Python)三语言解析 + 提供OJ在线评测