UVA11997K Smallest Sums(优先队列+二路归并）

本文主要是介绍UVA11997K Smallest Sums(优先队列+二路归并），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：UVA11997K Smallest Sums(优先队列+二路归并）

题目大意：求K个最小和。给出K行，每行有K个数，在每行中取一个元素相加，求这些和中最小的k的值。

解题思路：每一行排列一下，那么对于两张表a1< a2 < a3 < a4... ，可以将a1 + b1（最小的）, a1+ b2, a1 + b3...a1 + bk存到优先队列中，然后最小的出队，就尝试将剩余和中

                                                                            b1 < b2 < b3 < b4...

相应较小的存入优先队列，b1 + a2。求这个数值的时候，只需要知道a的下标就可以求到。s1 = a1 + b1 ， s2 = b1 + a1 - a1 + a2 = s1 - a1 + a2。碰到K个表就将表两两二路归并。

代码：

#include <cstdio>
#include <queue>
#include <algorithm>using namespace std;const int N = 755;
int k;struct Item {int s, b;//Item () {}Item (int s, int b): s(s), b(b) {}bool operator < (const Item &a) const {return s > a.s;}
};priority_queue<Item> q;void merge (int *A, int *B, int *C) {while (!q.empty()) {q.pop();}for (int i = 0; i < k; i++) q.push (Item (A[i] + B[0], 0));	for (int i = 0; i < k; i++) {Item item = q.top();q.pop();C[i] = item.s;if (item.b + 1 < k) q.push (Item (item.s - B[item.b] + B[item.b + 1], item.b + 1));	}
}int main () {int A[N][N];while (scanf ("%d", &k) != EOF) {for (int i = 0; i < k; i++) {for (int j = 0; j < k; j++)scanf ("%d", &A[i][j]);sort (A[i], A[i] + k);}for (int i = 1; i < k; i++)merge (A[0], A[i], A[0]);for (int i = 0; i < k - 1; i++) 			printf ("%d ", A[0][i]);printf ("%d\n", A[0][k - 1]);}	return 0;
}

                                                       

这篇关于UVA11997K Smallest Sums(优先队列+二路归并）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---