首页 > 代码库 > 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(优先队列+二路归并)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。