题目描述
click the link below
https://www.acwing.com/problem/content/description/3642/
归并排序里面的归并思想 其实就是一个归并排序。。。
还以为学完基础课归并排序之后就再也用不到归并排序了还是遇到了
C++ 代码
#include <iostream>
using namespace std;
const int N = 210;
int a[N], q[N];
int main()
{
int n, m;
cin >> n;
for(int i = 0; i < n; i ++) cin >> a[i];
cin >> m;
for(int j = n; j < n + m; j ++) cin >> a[j];
int i = 0, j = n, k = 0;
while(i < n && j < n + m) //两个pointer任何一个没有走到结尾 就继续归并
{
if(a[i] <= a[j])
q[k ++] = a[i ++];
else q[k ++] = a[j ++];
}
//y总优雅的称之为“扫尾”
while(i < n) q[k ++] = a[i ++]; //最后肯定有一个没有到结尾 不知道哪一个那就都来一遍 二者只执行一个
while(j < n + m) q[k ++] = a[j ++]; //将最后的大爷(比较大的)都接在屁股后面
for(int i = 0; i < n + m; i ++) cout << q[i] <<' ';
return 0;
}