UVA 11997 K Smallest Sums——多路归并

UVA 11997 K Smallest Sums——多路归并

一开始没想出来，看了蓝书的题解才懂的。

详解参考蓝书P190

#include #include #include #include #include using namespace std;const int maxn = 800;int n, a[maxn][maxn];struct Item { int s, b; Item(int s, int b) : s(s), b(b) {} bool operator < (const Item &rhs) const { return s > rhs.s; }};void Merge(int *x, int *y, int *z) { priority_queue q; for (int i = 0; i < n; i++) q.push(Item(x[i]+y[0], 0)); for (int i = 0; i < n; i++) { Item item = q.top(); q.pop(); z[i] = item.s; int b = item.b; if (b + 1 < n) q.push(Item(item.s-y[b]+y[b+1], 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], a[0]); printf("%d", a[0][0]); for (int i = 1; i < n; i++) printf(" %d", a[0][i]); printf("\n"); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。