UVa 11997 K Smallest Sums (우선 대기 열 & k 길 병합 2 개 병합)

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=497&page=show_problem&problem=3148
사고방식: k 로 를 두 개의 병합 으로 전환시키다
전체 코드:

/*0.172s*/

#include
using namespace std;
const int maxn = 755;

int A[2][maxn];

struct Item
{
	int s, b; /// s=A[a]+B[b]，   a    ，     
	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 q; ///   
	for (int i = 0; i < n; i++)
		q.push(Item(A[i] + B[0], 0));
	for (int i = 0; i < n; i++)
	{
		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)); ///   A[a]+B[b+1]=s-B[b]+B[b+1]
	}
}

int main()
{
	int n;
	while (~scanf("%d", &n))
	{
		for (int j = 0; j < n; j++) scanf("%d", &A[0][j]);
		sort(A[0], A[0] + n);
		for (int i = 1; i < n; i++) ///           
		{
			for (int j = 0; j < n; j++) scanf("%d", &A[1][j]);
			sort(A[1], A[1] + n);
			merge(A[0], A[1], A[0], n);
		}
		printf("%d", A[0][0]);
		for (int i = 1; i < n; i++)
			printf(" %d", A[0][i]);
		putchar(10);
	}
	return 0;
}