AcWing 146. 序列

2022-03-18 09:59:09

给定m个序列，每个包含n个非负整数。

现在我们可以从每个序列中选择一个数字以形成具有m个整数的序列。

很明显，我们一共可以得到nm<?XML:NAMESPACE PREFIX = "[default] http://www.w3.org/1998/Math/MathML" NS = "http://www.w3.org/1998/Math/MathML" />nm个这种序列，然后我们可以计算每个序列中的数字之和，并得到nmnm个值。

现在请你求出这些序列和之中最小的n个值。

输入格式

第一行输入一个整数T，代表输入中包含测试用例的数量。

接下来输入T组测试用例。

对于每组测试用例，第一行输入两个整数m和n。

接下在m行输入m个整数序列，数列中的整数均不超过10000。

输出格式

对于每组测试用例，均以递增顺序输出最小的n个序列和，数值之间用空格隔开。

每组输出占一行。

数据范围

0<m≤10000<m≤1000,
0<n≤20000<n≤2000

输入样例：

输出样例：

3 3 4

  1 #include <iostream>
  2 #include <queue>
  3 #include <algorithm>
  4 #include <vector>
  5 using namespace std;
  6 
  7 const int N = 2010;
  8 typedef pair<int, int> PII;
  9 int m, n;
 10 
 11 int a[N], b[N], c[N];
 12 
 13 void merge() {
 14 	priority_queue<PII, vector<PII>, greater<PII>> heap;
 15 	for(int i = 0; i < n; ++ i) heap.push({a[0] + b[i], 0});
 16 	for(int i = 0; i < n; ++ i) {
 17 		auto t = heap.top();
 18 		int s = t.first, p = t.second;
 19 		c[i] = s;
 20 		heap.push({s - a[p] + a[p+1], p+1});
 21 	}
 22 	for(int i = 0; i < n; ++ i) a[i] = c[i];
 23 }
 24 /*把两组结果分组
 25 a1, a2, a3 ... an
 26 b1, b2, b3 ... bn
 27 
 28 分组
 29 a1+b1 a2+b1 a3+b1 ... an+b1
 30 a1+b2 a2+b2 a3+b2 ... an+b2
 31 a1+b3 a2+b3 a3+b3 ... an+b3
 32 .
 33 .
 34 .
 35 a1+bn a2+bn a3+bn ... an+bn
 36 因为a数组时有序的，所以可以得a+b数组也是有序的。
 37 所以每组的第一个就是当前组的最小值
 38 假设a1+b3是第一个最小值，然后就将它删除，再加入它所在的组第二小的数a2+b3
 39 然后和前面a1b(1..n)作比较（不包括删除的数）选出第二小的数。
 40 */
 41 int main() {
 42 	int T;
 43 	cin >> T;
 44 	while(T --) {
 45 		cin >> m >> n;
 46 		for(int i = 0; i < n; ++ i) cin >> a[i];
 47 		sort(a, a + n);
 48 		for(int i = 0; i < m; ++ i){
 49 			for(int j = 0; j < n; ++ j) cin >> b[j];
 50 			merge();
 51 		}
 52 		for(int i = 0; i < n; ++ i) cout << a[i] << " ";
 53 		cout << endl;
 54 	}
 55 	return 0;
 56 }