题目链接
https://vjudge.net/problem/UVA-11997
题意
给定k个数组，每个数组有k个值。从每个数组中选一个值，然后对所选值累加求和。问这k^k个和中最小的k个分别是多少。将其升序输出。
分析
参考自刘汝佳《白书》中解法：多路归并。
先考虑简化情况：k=2.k=2时，和有k^2个，将这k^2个元素排序后，前k个即为所求。
多路归并是归并排序的升级版。
算法过程：
将k^2个和分成k个有序数组，每个数组有k个元素。用优先队列来维护每个数组中的最小值，通过k次出队、入队就可以得到最终结果。
对于k>2的情况，两两合并即可。
代码
#include <bits/stdc++.h>
using namespace std;const int maxn=760;struct node
{int sum,p;//node(int sum,int p):sum(sum),p(p){}bool operator<(const node &o)const{return sum>o.sum;}};
void merge(int *a,int *b,int *c,int n)
{priority_queue<node> que;for(int i=0;i<n;i++)que.push(node{a[i]+b[0],0});for(int i=0;i<n;i++){node t=que.top();que.pop();c[i]=t.sum;if(t.p+1<n) que.push(node{t.sum-b[t.p]+b[t.p+1],t.p+1});}
}
int ac[maxn][maxn];
int main()
{int k;while(cin>>k){for(int i=0;i<k;i++)for(int j=0;j<k;j++)cin>>ac[i][j];for(int i=0;i<k;i++)sort(ac[i],ac[i]+k);for(int i=1;i<k;i++)merge(ac[0],ac[i],ac[0],k);for(int i=0;i<k;i++){if(i) cout<<" "<<ac[0][i];else cout<<ac[0][i];}cout<<endl;}return 0;
}