蓝桥集训之序列

蓝桥集训之序列

• 核心思想：多路归并

  • 每次将两个序列合并 –> 两序列n²个和中最小的n个 构成新序列

  • 第一行都是加b₁ 每次在最外面的元素中取最小(优先队列)

    • 

•   #include<iostream>
    #include<algorithm>
    #include<cstring>
    #include<queue>
    #include<vector>
    
    using namespace std;
    const int N = 2010;
    typedef pair<int,int> PII;
    
    int a[N],b[N],c[N];
    int n,t,m;
    
    void merge()
    {
        priority_queue<PII,vector<PII>,greater<PII>> pq;
        for(int i=0;i<n;i++) pq.push({a[0] + b[i] , 0});  //将初始n个数加入优先队列
        for(int i=0;i<n;i++)
        {
            auto t = pq.top();  //取出最小
            pq.pop();
            int x = t.first , y = t.second;
            c[i] = x;
            pq.push({x - a[y] + a[y+1] , y+1});  //把后一个补上
        }
        memcpy(a, c, sizeof a);  //a[i] = c[i]更新a数组
    }
    int main()
    {
        cin>>t;
        while(t--) {
            cin >> m >> n;
            for (int i = 0; i < n; i++) scanf("%d", &a[i]);
            sort(a, a + n);
    
            for (int i = 0; i < m - 1; i++)
            {
                for(int j=0;j<n;j++)
                    scanf("%d",&b[j]);  //每输出一组 就合并
                merge();
            }
            for(int i=0;i<n;i++) printf("%d ", a[i]);
            puts(" ");
        }
    }