#全站唯一#T31220.序列合并题解
2024-10-13 17:44:22
发布于：湖南
35阅读
0回复
0点赞
原题链接：https://www.acgo.cn/problemset/info/31220 欢迎挑战（
根据题意，我们需要找到两个序列 和 中各取一个数相加后得到的前 小的和。由于 和 的范围较大，直接计算所有可能的和并排序的方法会非常耗时。因此，我们需要一种更高效的方法来解决这个问题。
那什么方法更高效呢？这就不得不提到最小堆（优先队列）了，
我们可以使用最小堆（优先队列）来高效地找到前 小的和。具体步骤如下：
首先将 和 中的最小元素相加的结果放入最小堆中。
每次从堆中取出最小的和，并将其对应的 和 中的下一个可能的和放入堆中。
重复2：直到找到前 小的和。
c++ code：
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef pair<int, int> pii;
struct Compare {
bool operator()(const pair<int, pii>& a, const pair<int, pii>& b) {
return a.first > b.first;
}
};
vector<int> findKSmallestSums(vector<int>& A, vector<int>& B, int K) {
int N = A.size();
sort(A.begin(), A.end());
sort(B.begin(), B.end());
priority_queue<pair<int, pii>, vector<pair<int, pii>>, Compare> minHeap;
minHeap.push({A[0] + B[0], {0, 0}});
vector<int> result;
while (K > 0 && !minHeap.empty()) {
auto top = minHeap.top();
minHeap.pop();
int sum = top.first;
int i = top.second.first;
int j = top.second.second;
result.push_back(sum);
K--;
if (i + 1 < N) {
minHeap.push({A[i + 1] + B[j], {i + 1, j}});
}
if (i == 0 && j + 1 < N) {
minHeap.push({A[i] + B[j + 1], {i, j + 1}});
}
}
return result;
}
int main() {
int N, K;
cin >> N >> K;
vector<int> A(N), B(N);
for (int i = 0; i < N; ++i) {
cin >> A[i];
}
for (int i = 0; i < N; ++i) {
cin >> B[i];
}
vector<int> result = findKSmallestSums(A, B, K);
for (int sum : result) {
cout << sum << " ";
}
cout << endl;
return 0;
}
排序 和 的时间复杂度为 ，每次从堆中取出元素和插入元素的时间复杂度为 ，总共需要 次操作，因此总时间复杂度为
使用了优先队列和一些辅助空间，空间复杂度为
python code:
import heapq
def find_k_smallest_sums(N, K, A, B):
A.sort()
B.sort()
# 最小堆，存储 (和, A的索引, B的索引)
min_heap = [(A[0] + B[0], 0, 0)]
visited = set((0, 0))
result = []
while K > 0 and min_heap:
current_sum, i, j = heapq.heappop(min_heap)
result.append(current_sum)
K -= 1
if i + 1 < N and (i + 1, j) not in visited:
heapq.heappush(min_heap, (A[i + 1] + B[j], i + 1, j))
visited.add((i + 1, j))
if j + 1 < N and (i, j + 1) not in visited:
heapq.heappush(min_heap, (A[i] + B[j + 1], i, j + 1))
visited.add((i, j + 1))
return result
N, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
result = find_k_smallest_sums(N, K, A, B)
print(" ".join(map(str, result)))
有帮助，赞一个