题目描述
给定m个序列,每个包含n个非负整数。
现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。
很明显,我们一共可以得到$n^m$个这种序列, 然后我们可以计算每个序列中的数字之和,并得到$n^m$个值。
现在请你求出这些序列和之中最小的n个值。
样例
输入样例:
1
2 3
1 2 3
2 2 3
输出样例:
3 3 4
算法1
(n路归并) $O(mnlogn)$
对于原来的m个数列,求最小的n个序列和。
可以对这m个数列进行合并,合并完之后的前n个数即为所求。
具体:
先考虑两个数组合并。
对a数组进行排序, 然后合并a,b两个数组。
$$
a_1, a_2, … a_n \\\
b_1, b_2, … b_n
$$
将两组数列这样分组。
$$
a_1 + b_1,\ a_2 + b_1, …,\ a_n + b_1 \\\
a_1 + b_2,\ a_2 + b_2, …,\ a_n + b_2 \\\
…\\\
a_1 + b_n,\ a_2 + b_n, …,\ a_n + b_n \\\
$$
由于a是有序的,所以最小n个数就是第一列。
如法炮制m - 1次,就可以求得最小的n个序列和;
但还有个问题需要解决,怎么找到pop
出的第一个最小值($a_1 + b_1$)后,怎么加入该数后面的数($a_2 + b_1$)
只要需要将前一个数的和 + 下一组的下标对应的值 - 前一个下标对应的值即可。+a[t.second + 1] - a[t.second]
其中t = heap.top();
时间复杂度
排序需要 $nlogn$, m路归并需要$m - 1$次归并 所以总共时间复杂度$O(mnlogn)$
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 2010;
int T, n, m;
int a[N], b[N], c[N];
void work(){
priority_queue<PII, vector<PII>, greater<PII>> heap;
for (int i = 0; i < n; i ++) heap.push({a[0] + b[i], 0});
for (int i = 0; i < n; i ++){
auto t = heap.top();
heap.pop();
c[i] = t.first;
heap.push({t.first + a[t.second + 1] - a[t.second], t.second + 1});
}
memcpy(a, c, sizeof c);
}
int main(){
cin >> T;
while (T --){
cin >> m >> n;
for (int i = 0; i < n; i ++) cin >> a[i];
sort(a, a + n);
for (int i = 0; i < m - 1; i ++){
for (int j = 0; j < n; j ++) cin >> b[j];
work();
}
for (int i = 0; i < n; i ++) printf("%d ", a[i]);
puts("");
}
return 0;
}