#全站唯一#T31220.序列合并题解
2024-12-22 20:48:17
发布于：湖南
49阅读
0回复
0点赞
原题链接：https://www.acgo.cn/problemset/info/31220
题目分析:
根据题意，我们需要找到两个序列 和 中各取一个数相加后得到的前 小的和
由于和的范围很大，直接计算所有可能的和并排序的方法会TLE
因此，我们可以使用最小堆(优先队列)来高效地找到前小的和
具体步骤:
首先将和中最小元素相加的结果放入最小堆中
然后每次从堆中取出最小的和，并将其对应的和中的下一个可能的和放入堆中，重复直到找到前小的和。
代码如下：
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
typedef pair<int,int>pii;
struct C{bool operator()(const pair<int,pii>&a,const pair<int,pii>&b){return a.first>b.first;}};
vector<int>f(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>>,C>m;
m.push({a[0]+b[0],{0,0}});
vector<int>r;
while(k>0&&!m.empty()){
auto t=m.top();
m.pop();
int s=t.first;
int i=t.second.first;
int j=t.second.second;
r.push_back(s);
k--;
if(i+1<n){m.push({a[i+1]+b[j],{i+1,j}});}
if(i==0&&j+1<n){m.push({a[i]+b[j+1],{i,j+1}});}}return r;}
int main(){
cin.tie(nullptr)->sync_with_stdio(0);
cout.tie(nullptr)->sync_with_stdio(0);
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>r=f(a,b,k);
for(int s:r){cout<<s<<" ";}
cout<<endl;
return 0;
}
有帮助，赞一个