#全站唯一#T31220.序列合并题解
2025-04-01 19:31:13
发布于：湖南
66阅读
0回复
0点赞
由于和的范围很大，直接暴力算所有可能的和并排序会TLE
但我们可以用优先队列找前小的和
具体就是将和中的 元素相加的和放进队列
然后每次从队列取最小和，并将其对应的 和 中下一个可能的和放进队列，重复到找到前 小的和并输出即可AC
代码如下：
#include <bits/extc++.h>
#define int long long
#define _x first
#define _y second
#define srt_a sort(a.begin(),a.end());
#define srt_b sort(b.begin(),b.end());
using namespace std;
typedef pair <int, int> pii;
struct c
{
bool operator()(const pair<int, pii>& a,const pair<int,pii>& b)
{
return a._x > b._x;
}
};
vector<int> solve(vector<int>& a,vector<int>& b,int k)
{
int n(a.size());
srt_a
srt_b
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._x);
int i(t._y._x);
int j(t._y._y);
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;
}
signed main()
{
ios::sync_with_stdio(false);cin.tie(NULL);
//int t;cin>>t;while(t--){}
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(solve(a,b,k));
for (int s:r) cout<<s<<' ';
cout<<'\n';
}
有帮助，赞一个