uva11997(優先隊列，歸並)

uva11997(優先隊列，歸並)

題意：

ｋ個數組，每個數字ｋ個值；

如果每個數組取一個值相加，那麼總共有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;
}