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
#include<iostream> #include<queue> #include<algorithm> using namespace std; const int MAXN=1000; struct Node{ int s,b; }; int B[MAXN]; bool operator <(Node a, Node b) { return a.s>b.s?true:false; } priority_queue<Node> a,b; int main() { int i,j,k; Node tmp; while(cin>>k) { for(i=0;i<k;i++) { cin>>tmp.s; a.push(tmp); } for(i=1;i<k;i++) { for(j=0;j<k;j++) cin>>B[j]; sort(B,B+k); while(!b.empty()) b.pop(); while(!a.empty()) { tmp=a.top(); a.pop(); tmp.b=0; tmp.s+=B[0]; b.push(tmp); } while(a.size()<k) { a.push(b.top()); tmp=b.top(); tmp.s=tmp.s-B[tmp.b]+B[tmp.b+1]; tmp.b++; b.pop(); b.push(tmp); } } while(!a.empty()) { tmp=a.top(); if(a.size()==1) cout<<tmp.s<<endl; else cout<<tmp.s<<' '; a.pop(); } } return 0; }