K Smallest Sums（排序）


You’re given k arrays, each array has k integers. There are k
k 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).
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
Sample Output
9 10 12
2 2
题意：有k个数组每个数组有k个数，取每个数组中的一个数相加，在加得的数中输出最小的k个数


题解：sort对每个数组进行排序，取前两个数组相加，求得最小的k个数记录下来，再将这k个数与下一个数组相加。数组两两相加时用优先队列，使得复杂度为O(n)（若不考虑优先队列）。


#include #define ll long long #define MT(a,b) memset(a,0,sizeof(a)); using namespace std; const int maxn=1e3+5; int n; struct dd { int v,id; dd (){} dd (int v,int id):v(v),id(id){} bool operator<(const dd &a)const { return a.v>n) { MT(a,0); for(int i=0;i>a[i][j]; sort(a[0],a[0]+n); for(int i=0;iQ; sort(a[i+1],a[i+1]+n); for(int j=0;j