K Smallest Sums（多路合并）

问题 E: K Smallest Sums（多路合并）

时间限制: 1.000 Sec 内存限制: 128 MB

题目描述

给定 k 个数组，每个数组中都有 k 个整数。

从每个数组中各选取一个元素，一共可以形成 kk 种不同的组合方式，每种组合的和为所选元素之和。

你的任务是找出所有这些组合中 最小的 k 个和，并按升序输出。

输入

输入包含若干组测试数据。

每组数据的格式如下：

第一行包含一个整数 k（2≤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小的数，接下来对于a1，a2，ak，b1，b2，bk，先按a数组和b0合并，每次遍历到某个，在优先队列里面插入a+bi+1，从而保证能在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) { vector<vector<int>> a(n, vector<int>(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()); } // 优先队列默认大根堆，最大值在堆顶 vector<int> A(n); for(int i=0;i<n;i++)A[i]=a[0][i]; for (int i = 1; i < n; i++) { priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq; for(int j=0;j<n;j++)pq.push({A[0]+a[i][j],j}); vector<int> res; vector<int> pos(n,0); for(int k=0;k<n;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}); } A=res; } for(int i=0;i<n;i++)cout<<A[i]<<" "; cout<<"\n"; } return 0; }