POJ 2442 Sequence

想法：
　　這題與UVa 11997一樣，差別只在於UVa那題是K行K個數字，這題是M行N個數字，詳細過程我寫在UVa 11997 K Smallest Sums。

	#include <cstdio>
	#include <algorithm>
	#include <queue>
	using namespace std;
	struct custom_type {
	int val;
	int pos;
	bool operator < (const custom_type &B) const {
	return val > B.val; // min heap
	}
	};
	int main()
	{
	int T ,M, N, L1[2001], L2[2001];
	scanf("%d", &T);
	while (T--) {
	scanf("%d %d", &M, &N);
	for (int i = 0; i < N; ++i) scanf("%d", &L1[i]);
	sort(L1, L1 + N);
	for (int k = 1; k < M; ++k) {
	for (int i = 0; i < N; ++i) scanf("%d", &L2[i]);
	sort(L2, L2 + N);
	priority_queue<custom_type> PQ;
	for (int i = 0; i < N; ++i)
	PQ.push({L1[i] + L2[0], 0});
	for (int i = 0; i < N; ++i) {
	custom_type tmp = PQ.top();
	PQ.pop();
	L1[i] = tmp.val;
	if (tmp.pos+1 < N)
	PQ.push({tmp.val - L2[tmp.pos] + L2[tmp.pos+1], tmp.pos + 1});
	}
	}
	for (int i = 0; i < N - 1; ++i)
	printf("%d ", L1[i]);
	printf("%d\n", L1[N-1]);
	}
	}

view raw [POJ] 2442 Sequence.cpp hosted with ❤ by GitHub