两个序列求前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;
}

巴特西

两个序列求前k大和

最新文章

热门文章