数据是十万，所以考虑
O
(
N
l
o
g
N
)
O(NlogN)
O(NlogN)以下的解法。因为是TopK问题，所以暗示用堆，每次从堆中取出最大值，所以需要大根堆。放入堆中的元素不能有重复，因此要使用哈希表判重。另外，最大值只能是两种情况。
a数组往前移动一格，a[i-1] + b[j]
b数组往前移动一格，a[i] + b[j-1]
所以每次将这两种值扔进大根堆中，取出k个值即为答案。
代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N], b[N];
using LL = long long;
using VT = vector<LL>;
int main(){
int n, k;
cin>>n>>k;
for(int i = 0; i < n; i++) cin>>a[i];
for(int i = 0; i < n; i++) cin>>b[i];
sort(a, a+n);
sort(b, b+n);
priority_queue<VT> pq;
pq.push({a[n-1]+b[n-1],n-1,n-1});
unordered_set<pair<int, int>> st;
while(k--){
auto t =pq.top();
pq.pop();
int sum = t[0], i=t[1],j=t[2];
printf("%d ",sum);
if(i && !st.count({i-1,j})){
st.insert({i-1, j});
pq.push({a[i-1]+b[j],i-1,j});
}
if(j && !st.count({i,j-1})){
st.insert({i, j-1});
pq.push({a[i]+b[j-1],i,j-1});
}
}
return 0;
}