首页 > 代码库 > UVA 11997 - K Smallest Sums(优先队列+多路合并)
UVA 11997 - K Smallest Sums(优先队列+多路合并)
UVA 11997 - K Smallest Sums
题目链接
题意:给定k个数组,每一个数组k个数字,要求每一个数字选出一个数字,构成和,这样一共同拥有kk种情况,要求输出最小的k个和
思路:事实上仅仅要能求出2组的前k个值,然后不断两两合并就能够了,由于对于每两组,最后答案肯定是拿前k小的去组合。然后问题就变成怎么求2组下的情况了,利用一个优先队列维护,和作为优先级,先把原数组都从小到大排序好了,那么先把a[i] + b[0] (i < k)入队,然后往后取k个,每次取完之后,拿最小那个在把b往后推一个,这样保证每次队列中都会有当前的最小值存在,利用优先队列取出就可以,总复杂度为O(k2log(k))
代码:
#include <cstdio> #include <cstring> #include <algorithm> #include <queue> using namespace std; const int N = 755; int n, a[N][N]; struct State { int b, sum; State() {} State(int b, int sum) { this->b = b; this->sum = sum; } bool operator < (const State& c) const { return sum > c.sum; } }; void merge(int *a, int * b) { priority_queue<State> Q; for (int i = 0; i < n; i++) Q.push(State(0, a[i] + b[0])); for (int i = 0; i < n; i++) { State now = Q.top(); a[i] = now.sum; Q.pop(); Q.push(State(now.b + 1, now.sum - b[now.b] + b[now.b + 1])); } } int main() { while (~scanf("%d", &n)) { 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]); for (int i = 0; i < n - 1; i++) printf("%d ", a[0][i]); printf("%d\n", a[0][n - 1]); } return 0; }
UVA 11997 - K Smallest Sums(优先队列+多路合并)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。