题意：
ｋ个数组，每个数字ｋ个值；
如果每个数组取一个值相加，那么总共有k^k种结果，取前ｋ小的值，输出；
?
思路：
首先我们两个数组，两个数组找出前ｋ小的和了，在加入第三个，这样一直两两算；
因为两个数组取出前ｋ小的和了；那么加入第三个数组后，那么新的前ｋ小肯定是第三个数组的值和那之前前ｋ的值的和；
而求两个数组，和的前ｋ小，我们可以用优先队列，加上一个动态规划；
只有AB两个数组.
那么S = A[i] + B[j] 就可以推出A[i] +Ｂ[j + 1]；
即Ｓ － Ｂ［ｊ］ ＋B[j +１];
具体可以看刘汝佳书里的解析；
?
?
#include#include #include #include using namespace std; struct point { int s, b; point(int a, int c) { s = a; b = c; } bool operator <(point a)const { return this->s > a.s; } }; const int N = 1000; int A[N][N]; int n; void merge(int* A, int* B, int* C, int n) { priority_queue q; for(int i = 0; i < n; i++) q.push(point(A[i] + B[0], 0)); for(int i = 0; i < n; i++) { point p = q.top(); q.pop(); C[i] = p.s; int b = p.b; if(b + 1 < n) q.push(point(p.s - B[b] + B[b + 1], b + 1)); } } int main() { while(scanf("%d",&n) == 1) { 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], n); printf("%d",A[0][0]); for(int i = 1; i < n; i++) { printf(" %d",A[0][i]); } printf("\n"); } return 0; }
?