---
title: "序列"
created: 2025-11-28
tags:
  - 算法
---

# 序列

## 题目 [序列](https://www.acwing.com/problem/content/148/)

![[image-2ec4ad75.png]]

## 思路分析

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个数

![[image-10b69bf5.png]]

![[image-4186763d.png]]

![[image-27b784ef.png]]

## 代码实现

```cpp
#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-刷题理模型]] ➡️ [[推荐系统|推荐系统]]