学步园

【特别注意】：这个方法有问题，正确的方法是用堆实现，最近比较忙，没时间写代码，过一段时间补上。

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

#include <stdio.h>
#define M 6
#define N 8
int a1[M] = {1,3,5,6,9,10};
int a2[M] = {2,2,3,3,5,11};
int x = 0;
int y = 0;
int result[N] = {0};

int min(int a, int b){
	return a<b?a:b;
}

int main(){
	int i = 0;
	int h = 1;
	int index = 0;
	int max_index = 5;
	result[index++] = a1[x]+a2[y];
	while(1){
		//固定x，y先前走，直到和大于a[x+1][y]
		h = 1;
		while(a1[x] + a2[y+h] <= a1[x+1] + a2[y]){
			result[index++] = a1[x] + a2[y+h];
			if(index == max_index) break;
			h++;
		}
		result[index++] = a1[x+1] + a2[y];
		if(index == max_index) break;
		x++;

		//固定y，x先前走，直到和大于a[x][y+1]
		h = 1;
		while(a1[x+h] + a2[y] <= a1[x] + a2[y+1]){
			result[index++] = a1[x+h] + a2[y];
			if(index == max_index) break;
			h++;
		}
		result[index++] = a1[x] + a2[y+1];
		if(index == max_index) break;
		y++;
	}

	printf("结果是：\n");
	for(i=0;i<5;i++)
		printf("%d ",result[i]);
	return 0;
}

运行结果：