序列

题目 序列

思路分析

1:首先我们思考如何将两个序列合并，假如有两个序列a[n], b[n], 如下：

1: a1, a2, a3, …., an;

2: b1, b2, b3, ….., bn;

先将a[n]排序, 则所有在a[n], b[n]中任意挑选两个数，他们的和为:

b1 + a1, b1 + a2, b1 + a3, …., bn + an;

b2 + a1, b2 + a2, b2 + a3, …., b2 + an;

. . .

bn + a1, bn + a2, bn + a3, …., bn + an;

因为a[n]是从小到大排列的所以第一列肯定是最小的数，

然后我们需要每次选择最小第一列中最小的数，

假设第一列中 b1 + a1 最小

那么下次我们要从b1 + a2, b2 + a1, b3 + a1, …, bn + a1中选择一个最小的数，

将这个最小的数记录到c[n]中，最后c[n]即是这两排合并的最小的数，且是从小到大排序的,

然后再将c[n]都记录到a[n], 再次重复上面的操作m - 1次，即最后a[n]记录的就是最小的前n个数

代码实现

#include<bits/stdc++.h>

using namespace std;

typedef pair<int,int> PII;

const int N=2e3+10;

int a[N],b[N],c[N];

int n,m,T;

void merge(){

    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();

        int s=t.first,p=t.second;

        c[i]=s;

        heap.push({s-a[p]+a[p+1],p+1});

    }

    memcpy(a,c,4*n);

}

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=1;i<m;i++){

            for(int j=0;j<n;j++)

                cin>>b[j];

            merge();

        }

        for(int i=0;i<n;i++){

            if(i>0)

                cout<<" ";

            cout<<a[i];

        }

        cout<<endl;

    }

    return 0;

}

同类题型

视频讲解

⬅️ 多路归并相关问题 🏠 00-刷题理模型 ➡️ 推荐系统