两个序列求前k大和

时间:2023-03-09 00:06:02
两个序列求前k大和

---恢复内容开始---

没有题目,没有题意,这是学长提过的一个技巧,给你两个排好序的序列,每次可以各从中取一个,求前k大的和,

一个优先队列,先将a序列中最大的那个和b序列所有元素相加存进队列中,每次弹出最大的那个时(ai,bj),把(ai+1,bj)存进去,就行了;

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
int sum;
int x;
int y;
friend bool operator<(node a,node b)
{
return a.sum<b.sum;
}
}temp,ans;
int main()
{
int s=0;
priority_queue<node> q;
int n,k;
int m;
int a[20];
int b[20];
cin>>n>>m>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=m;i++)
cin>>b[i];
sort(a+1,a+1+n);
sort(b+1,b+1+m);
for(int i=1;i<=m;i++)
{
temp.sum=a[n]+b[i];
temp.x=n;
temp.y=i;
q.push(temp);
}
int cnt=0;
while(!q.empty())
{
cnt++;
if(cnt>k)
break;
ans=q.top();
s+=ans.sum;
temp.x=ans.x-1;
temp.y=ans.y;
temp.sum=a[ans.x-1]+b[ans.y];
q.pop();
q.push(temp);
}
cout<<s<<endl;
return 0;
}