题意：有n个数组，各包含n个元素，在每个数组里任意选出一个元素加起来，可以得到n^n个和，求这些和里中最小的n个值
思路：将每个数组排序后，拿两个数组来说，会有例如：
A1+B1 <= A1+B2 < ...
A2+B1 <= A2+B2...
......
......
分析Aa+Bb,我们用二元组（s,b）来表示，其中s = Aa+Bb,可以推出
Aa+B(b+1) = Aa+Bb-Bb+B(b+1) = s + B(b+1) - Bb，采用优先队列，每次选出最小的，依次推
#include#include #include #include #include using namespace std; const int MAXN = 768; struct node{ int s,b; node(int s,int b):s(s),b(b) {} bool operator <(const node &a) const{ return s > a.s; } }; int A[MAXN][MAXN],n; void merge(int *A,int *B,int *C){ priority_queue q; for (int i = 0; i < n; i++) q.push(node(A[i]+B[0],0)); for (int i = 0; i < n; i++){ node temp = q.top(); q.pop(); C[i] = temp.s; int b = temp.b; if (b+1 < n) q.push(node(temp.s-B[b]+B[b+1],b+1)); } } int main(){ 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; }