Acwing 146. 序列

Acwing 146. 序列

思路：

先考虑其中的两个数组，先把a数组排序。
则：

每一行都是有序的，且每一行的第一个数都是所在行的最小值。
问题转化为，如何取出前n个小的数。
需要注意的一点是：
每次合并的答案并不是每一行的第一个数，比如第一个小的数是b1 + a1，则第二小的数是有可能为b1 + a2的，因为b数组不是有序的，而且b是否有序，与b + a的和是独立的问题。

可以考虑使用优先队列，来处理最小数。
C存每一次的中间结果，a存在每次合并两个数组的结果，最后的答案就是a里面的元素。

代码：

#include<queue>
#include<iostream>
#include<algorithm>

using namespace std;
typedef pair<int, int> PII;

const int N = 2003;
int a[N],b[N],c[N];
int T;
int n,m;

void merge(){
    priority_queue<PII, vector<PII>, greater<PII>> q;
    for(int i = 0; i < m; i++){
        q.push({b[i] + a[0], 0});
    }
    
    for(int i = 0; i < m; i++){
        auto t = q.top();
        q.pop();
        int x = t.first, y = t.second;
        c[i] = x;
        q.push({x - a[y] + a[y + 1], y + 1});
    }
    for(int i = 0; i < m; i++) a[i] = c[i];
    
}

int main(){
    cin >> T;
    while(T--){
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            cin >> a[i];
        }
        sort(a, a + m);
        for(int i = 0; i < n - 1; i++){
            for(int j = 0; j < m; j++) cin >> b[j];
            merge();
        }
        for(int i = 0; i < m; i++) cout << a[i] << " ";
        puts("");
    }
    return 0;
}