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

题目：有两个序列A和B,A=(a1,a2,...,ak),B=(b1,b2,...,bk),A和B都按升序排列，对于1<=i,j<=k，求k个最小的（ai+bj），要求算法尽量高效 .

解法：本题可借助最小堆来解决，由于a1+b1肯定是最小的和，首先把a1+b1的结果放大最小堆里，此时堆中只有一个元素，自然满足最小堆条件，然后开始出堆的操作，从堆里面取出根节点（也就是最小的值），假如此时堆顶元素为ai+bi,则需要像最小堆中压入a(i+1)+bj的和与ai+b(j+1)的和，当然，要保证下标不越界，如果下标越界了则忽略，另外要保证已经压入过堆中的组合（即使已经从堆中被取出了的）不再被压入堆中。不断地进行出堆、入堆的操作，重复k次，就得到了k个最小的组合值。

代码如下：

#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;
}

由于堆的最大深度为logk,所以时间复杂度为klogk数量级,空间复杂度O(k).