K Smallest Sums（多路合并）

问题 E: K Smallest Sums多路合并时间限制: 1.000 Sec 内存限制: 128 MB题目描述给定 k 个数组每个数组中都有 k 个整数。从每个数组中各选取一个元素一共可以形成 kk 种不同的组合方式每种组合的和为所选元素之和。你的任务是找出所有这些组合中 最小的 k 个和并按升序输出。输入输入包含若干组测试数据。每组数据的格式如下第一行包含一个整数 k2≤k≤750接下来的 k 行每行包含 k 个正整数表示一个数组每个整数不超过 1,000,000。输出对于每组测试数据输出 最小的 k 个和按升序排列用空格分隔。样例输入3 1 8 5 9 2 5 10 7 6 2 1 1 1 2样例输出9 10 12 2 2我们分析这个问题直接能想到差分计算大小然而不同的组合不好实现。利用递推/递归思想我们不妨改变为每次把k个小数和前面的合并贪心思想考虑到和下一个合并的一定是上一个的前k小的数接下来对于a1a2akb1b2bk先按a数组和b0合并每次遍历到某个在优先队列里面插入abi1从而保证能在k次内得到k个最小数代码实现如下#include iostream #include vector #include algorithm #include vector #include cmath #include queue #include set #include cstring #include string #include climits using namespace std; int main() { ios::sync_with_stdio(0); cin.tie(0); int n; while (cin n) { vectorvectorint a(n, vectorint(n)); for (int i 0; i n; i) for (int j 0; j n; j) cin a[i][j]; for (int i 0; i n; i) { sort(a[i].begin(), a[i].end()); } // 优先队列默认大根堆最大值在堆顶 vectorint A(n); for(int i0;in;i)A[i]a[0][i]; for (int i 1; i n; i) { priority_queuepairint, int, vectorpairint, int, greaterpairint, int pq; for(int j0;jn;j)pq.push({A[0]a[i][j],j}); vectorint res; vectorint pos(n,0); for(int k0;kn;k) { auto [x,y]pq.top(); pq.pop(); res.push_back(x); pos[y]; if(pos[y]n)pq.push({A[pos[y]]a[i][y],y}); } Ares; } for(int i0;in;i)coutA[i] ; cout\n; } return 0; }