﻿ 有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升 - 鸿网互联

# 有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升

```#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef struct sum_info
{
int value;
int i;
int j;
}sum_info;
struct cmp
{
bool operator()(sum_info a,sum_info b)
{
if(a.value>b.value)
return true;
else
return false;
}
};
int *min_k(int *A,int *B,int k);
int main()
{
int k;
cin>>k;
int *A=new int[k];
int *B=new int[k];
int i;
for(i=0;i<k;i++)
cin>>A[i];
for(i=0;i<k;i++)
cin>>B[i];
int *result=min_k(A,B,k);
if(result!=NULL)
{
for(i=0;i<k;i++)
cout<<result[i]<<" ";
cout<<endl;
delete []result;
}
delete []A;
delete []B;
return 0;
}
int *min_k(int *A,int *B,int k)
{
if(A==NULL||B==NULL||k<=0)
return NULL;
priority_queue<sum_info,vector<sum_info>,cmp> q;//STL中的优先级队列是借助堆实现的，这里为了方便直接使用优先级队列
sum_info tmp;
tmp.value=A[0]+B[0];
tmp.i=0;
tmp.j=0;
q.push(tmp);
int *result=new int[k];
int count,i,j;
count=0;
while(count<k)
{
tmp=q.top();
result[count++]=tmp.value;
i=tmp.i;
j=tmp.j;
q.pop();
sum_info a,b;
if((i+1)<k)
{
a.i=i+1;
a.j=j;
a.value=A[i+1]+B[j];
q.push(a);
}
if((j+1)<k)
{
b.i=i;
b.j=j+1;
b.value=A[i]+B[j+1];
q.push(b);
}
}
return result;
}
```

<