K Smallest SumsYou'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.InputThere 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.OutputFor each test case, print the k smallest sums, in ascending order.Sample Input3 1 8 5 9 2 5 10 7 6 2 1 1 1 2 Output for the Sample Input9 10 122 2思路：将k个数组，两两进行归并，求出前n个sum最小的，最后合并的数组便是结果（贪心性质）node中b用来记录上一个最小的和加入的b的位置，每次弹出当前最小的sum的解，然后将下一个b加入进去代码如下：#include #include #include #include #include using namespace std; struct node { int sum,b; node(int sum,int b):sum(sum),b(b){} friend bool operator < (node a,node b) { return a.sum > b.sum; } }; //每次合并出前n个最小的（贪心合并） void merge_all(int *a,int *b,int *c,int n) { priority_queue pq; for(int i = 0 ; i < n ;i++) { pq.push(node(a[i]+b[0],0)); } for(int i = 0 ; i < n ;i++) { node temp = pq.top(); pq.pop(); c[i] = temp.sum; if(temp.b+1 < n) { pq.push(node(c[i]-b[temp.b]+b[temp.b+1],temp.b+1)); } } } int main () { int n,t; while(scanf("%d",&n)!=EOF) { int num[n][n]; for(int i = 0 ; i < n ; i++) { for(int j = 0 ; j < n ;j++) { scanf("%d",&num[i][j]); } sort(num[i],num[i]+n); } for(int i = 1 ; i < n ;i++) { merge_all(num[0],num[i],num[0],n); } printf("%d",num[0][0]); for(int i = 1 ; i < n ;i++) { printf(" %d",num[0][i]); } printf(" "); } return 0; }