题目链接:点击进入 先考虑两个数组A,B的情况,这样总共有n^2种情况;将A,B数组排序后,我们可以将所有情况组织成n张表: 表1: A[1]+B[1]<=A[1]+B[2]<=……<=A[1]+B[n]. 表2: A[2]+B[1]<=A[2]+B[2]<=…….<=A[2]+B[n]. ……. 表n: A[n]+B[1]<=A[n]+B[2]<=……..<=A[n]+B[n] 这n张表都是有序的,所以可以以多路归并的思想求出其中前n个最小的元素.对于这个题目,有k个数组,我们可以采取两两合并的方式进行.
代码如下:
;const int maxn=760;int A[maxn][maxn];typedef struct node{int sum,index; ///保留a[i]+b[index]的值和b[]的下标node(int s,int i){sum=s; index=i;}bool operator < (const node& n1) const{return sum>n1.sum;}}P;P p1(0,0);int n;void Merge(int *a,int *b,int *c)///对a,b两个数组求前n个最小值{ ///使用的是多路归并的思想priority_queue<P>q;for(int i=0;i<n;i++)q.push(node(a[i]+b[0],0));for(int i=0;i<n;i++){p1=q.top(); q.pop(); ///取出最小的一个值c[i]=p1.sum;int j=p1.index;if(j+1<n) ///将目前最小值列的下一个值放入优先队列q.push(node(p1.sum-b[j]+b[j+1],j+1));}}int main(){freopen(“in.txt”,”r”,stdin);while(scanf(“%d”,&n)!=EOF){for(int i=0;i<n;i++){for(int j=0;j<n;j++)scanf(“%d”,&A[i][j]);sort(A[i],A[i]+n);}for(int i=1;i<n;i++)Merge(A[0],A[i],A[0]);printf(“%d”,A[0][0]);for(int i=1;i<n;i++)printf(” %d”,A[0][i]);printf(“\n”);} return 0;}
，人生谁无少年时，甜苦酸辛各自知。
