Problem K
K Smallest Sums
You're given k arrays, each array has k integers. There are kk ways to pick exactly one element in each array and calculate the sum of the integers. Your task is to find the k smallest sums among them.
Input
There will be several test cases. The first line of each case contains an integer k (2<=k<=750). Each of the following k lines contains k positive integers in each array. Each of these integers does not exceed 1,000,000.
The input is terminated by end-of-file (EOF). The size of input file does not exceed 5MB.
Output
For each test case, print the k smallest sums, in ascending order.
Sample Input
3 1 8 5 9 2 5 10 7 6 2 1 1 1 2
Output for the Sample Input
9 10 12 2 2
Rujia Liu's Present 3: A Data Structure Contest Celebrating the 100th Anniversary of Tsinghua University
Special Thanks: Yiming Li
Note: Please make sure to test your program with the gift I/O files before submitting!
题目是一道经典的多路合并的题目,一直都没有注意一些细节,觉得自己懂了,就瞎写,今天换了一个环境,破釜沉舟吧,
加油。不谢的努力,你应该能够成功。
这个题目还是有个小模版的就是优先队列维护二路合并的最小和,
当然,k路合并,就是依次两路合并贪心过去。
真的比较不错,一会还得去找找多路合并的题目;
贴出代码:
#include <stdio.h> #include <string.h> #include <iostream> #include <string> #include <queue> #include <algorithm> using namespace std; int A[770][770]; int K; struct Node { int sum; int y; bool operator < (const Node& t) const { return sum > t.sum; } }node; void merge(int* a, int* b, int* c) { priority_queue <Node> Q; for (int i = 0; i < K; i++) { node.sum = b[0] + a[i]; node.y = 0; Q.push(node); } for (int i = 0; i < K; i++) { node = Q.top(); Q.pop(); c[i] = node.sum; int num = node.y; node.sum = node.sum - b[num] + b[num + 1]; node.y = num + 1; if (num + 1 < K) { Q.push(node); } } } int main() { 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; i++) { printf(i == K - 1 ? "%d\n" : "%d ", A[0][i]); } } // system("pause"); return 0; }