uva11997(优先队列，归并)

题意：

ｋ个数组，每个数字ｋ个值；

如果每个数组取一个值相加，那么总共有k^k种结果，取前ｋ小的值，输出；

思路：

首先我们两个数组，两个数组找出前ｋ小的和了，在加入第三个，这样一直两两算；

因为两个数组取出前ｋ小的和了；那么加入第三个数组后，那么新的前ｋ小肯定是第三个数组的值和那之前前ｋ的值的和；

而求两个数组，和的前ｋ小，我们可以用优先队列，加上一个动态规划；

只有AB两个数组.

那么S = A[i] + B[j] 就可以推出A[i] +Ｂ[j + 1]；

即Ｓ　－　Ｂ［ｊ］　＋B[j +１];

具体可以看刘汝佳书里的解析；

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
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<point> 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;
}

uva11997(优先队列，归并)

原文：http://blog.csdn.net/yeyeyeguoguo/article/details/44596697