1.题目描述：点击打开链接
2.解题思路：本题是多路归并问题，即有n个有序表，需要将这n个有序表合成一个有序表。多路归并问题的一般解法是利用优先队列解决，优先队列q中初始存入每个表的第一个元素，然后每次出一个元素，就把它放入新表，并将它所在的表的下一个元素值加入队列。
本题的关键点在于如何将这n组元素转化为上述多路归并问题。我们先考虑一个简化版本的问题，给出两个长度为n的有序表A和B，分别在A和B中任取一个数并相加，可以得到你n^2个和，求这些和中最小的n个和。我们可以把这n^2个和组织成如下n个有序表：
表1：A1+B1≤A1+B2≤A1+B3≤…
表2：A2+B1≤A2+B2≤A2+B3≤…
表3：A3+B1≤A3+B2≤A3+B3≤…
……
表n：An+B1≤An+B2≤An+B3≤…
这样，每个表的元素都是一个和值，按照上述的多路归并的解法合并后输出前n个和值即可。我们用二元组(s,b)表示一个元素，，其中s=A[a]+B[b]。这里有一个技巧：无需保存a的下标。因为下一个二元组(s’,b+1)可以通过递推式s’=A[a]+B[b+1]=A[a]+B[b]-B[b]+B[b+1]=s-B[b]+B[b+1]。并不需要知道a的下标。
推而广之，现在有n个表，怎么办呢？两两合并即可！比如表A[0]，A[1]先合并，新表还是A[0]（可以对表A[0]又读又写，因为找下一个s值不需要用到A[0]表中的元素了），这样合并后，表A[0]中的元素是前两个表的n^2个和值，接下来再和表A[2]合并，合并后表A[0]中的元素是前三个表的n^3个和值，以此类推即可。
不过本题有一个重要的技巧：无需把所有的n^n个和值都放到新表中，每次合并都只读取n个元素，并只放入n个元素到新表中即可。这样一来，每次合并的时间复杂度均为O(N*logN)，进行n次合并的时间复杂度是O(N^2*logN)。
3.代码：
#define _CRT_SECURE_NO_WARNINGS #include<iostream>#include<algorithm>#include<string>#include<sstream>#include<set>#include<vector>#include<stack>#include<map>#include<queue>#include<deque>#include<cstdlib>#include<cstdio>#include<cstring>#include<cmath>#include<ctime>#include<functional>using namespace std;struct Item{int s, b;Item(int s, int b) :s(s), b(b){}bool operator <(const Item&rhs)const{return s>rhs.s;}};void merge(int*A, int*B, int*C, int n){priority_queue<Item>q;for (int i = 0; i < n; i++)q.push(Item(A[i] + B[0], 0));//初始化for (int i = 0; i < n; i++)//一共只读取前n个元素，注意，不要以为初始化的前n个元素就是最小的{Item item = q.top(); q.pop();//取出A[a]+B[b]C[i] = item.s;int b = item.b;if (b + 1 < n)//存在下一个元素q.push(Item(item.s – B[b] + B[b + 1], b + 1));}}#define N 768int A[N][N];int main(){//freopen("t.txt", "r", stdin);int n;while (~scanf("%d", &n)){for (int i = 0; i < n; i++){for (int j = 0; j < n; j++)cin >> A[i][j];sort(A[i], A[i] + n);}for (int i = 1; i < n; i++)//两两合并merge(A[0], A[i], A[0], n);printf("%d", A[0][0]);for (int i = 1; i < n; i++)printf(" %d", A[0][i]);printf("\n");}return 0;}
观今宜鉴古，无古不成今。
