给定m个序列，每个包含n个非负整数。
现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。
很明显，我们一共可以得到nmnm个这种序列， 然后我们可以计算每个序列中的数字之和，并得到nmnm个值。
现在请你求出这些序列和之中最小的n个值。
第一行输入一个整数T，代表输入中包含测试用例的数量。
接下来输入T组测试用例。
对于每组测试用例，第一行输入两个整数m和n。
接下在m行输入m个整数序列，数列中的整数均不超过10000。
对于每组测试用例，均以递增顺序输出最小的n个序列和，数值之间用空格隔开。
每组输出占一行。
0<m≤10000<m≤1000,
0<n≤20000<n≤2000
1
2 3
1 2 3
2 2 3
3 3 4
算法：二叉堆（小根堆） + 数学归纳 + 贪心
题解：我们先看一下样例，可以分解为1+2 1+2 1+3 2+2 2+2 2+3 3+2 3+2 3+3这9个数，然后找出前3个最小的，答案自然就是3 3 4啦。
当m == 2时，我们先将数组a，b排序然后就可以得到这样一个序列和：
b[1]+a[1] b[1]+a[2] ...... b[1]+a[n]
b[2]+a[1] b[2]+a[2] ...... b[2]+a[n]
......
b[n]+a[1] b[n]+a[2] ...... b[n]+a[n]
其中的序列和都是从小到大排序的，因为a和b数组都是有序的，所以我们只要将序列和的第一个都放入小根堆中，如果当前的第一个取出来了，我就把第二个放入小根堆中，依此类推。
注意：其中a数组中的每个元素都是前面几个序列和的最小的n个元素。
#include <iostream> #include <cstdio> #include <queue> #include <algorithm> using namespace std; const int maxn = 2e3+7; priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q; int n, m; int a[maxn], b[maxn], c[maxn]; int main() { int T; scanf("%d", &T); while(T--) { scanf("%d %d", &m, &n); for(int i = 1; i <= n; i++) { scanf("%d", &a[i]); } sort(a + 1, a + n + 1); for(int j = 2; j <= m; j++) { while(!q.empty()) { //清空上一次获取前n个最小的数之后的无用值 q.pop(); } for(int i = 1; i <= n; i++) { scanf("%d", &b[i]); } sort(b + 1, b + n + 1); for(int i = 1; i <= n; i++) { q.push(make_pair(a[1] + b[i], 1)); } for(int i = 1; i <= n; i++) { pair<int, int> v = q.top(); q.pop(); c[i] = v.first; q.push(make_pair(v.first + a[v.second + 1] - a[v.second], v.second + 1)); //这里是移动a数组的下标，上次用到了a[v.second],所以这次要减掉，加上新的值 } for(int i = 1; i <= n; i++) { //把更新后的最小数组赋值给a数组 a[i] = c[i]; } } for(int i = 1; i <= n; i++) { printf("%d%c", a[i], " \n"[i == n]); } } return 0; }
AcWing：146. 序列（小根堆 + 数学归纳 + 贪心）
原文：https://www.cnblogs.com/buhuiflydepig/p/11326141.html