[数据结构与算法]【题解】【AcWing】1579. 插入还是归并

1579. 插入还是归并

原题传送：AcWing 1579. 插入还是归并

根据维基百科：

插入排序迭代，每次将一个插入元素插入到排好序的输出序列中，每次迭代插入排序都会从输入数据中移除一个元素，并在已排好序的序列中找到它所属的位置，然后将其插入。直到没有输入元素剩余为止。

归并排序的工作方式如下：将未排序的序列划分为 $N$ 个子序列，每个子序列包含 $1$ 个元素（将 $1$ 个元素的序列视为已排序）。然后重复合并两个相邻的子序列以产生新的排序子序列，直到仅剩 $1$ 个子序列为止。

现在，给定初始序列，以及经过某种排序方法多次迭代后的序列，请你判断我们使用的哪一种排序方法。

输入格式

第一行包含整数 $N$ ，表示序列中整数个数。

第二行包含 $N$ 个整数表示初始序列。

第三行包含 $N$ 个整数表示经过若干次迭代后的序列。

假定排序的目标序列总是递增的。

输出格式

第一行输出Insertion Sort或Merge Sort，以指明所采用的具体排序方法。

运用此方法再进行一次迭代，并在第二行输出本次迭代后的序列。

数据保证答案唯一。

数据范围

$1\le N\le 100$

输入样例1：

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出样例1：

Insertion Sort
1 2 3 5 7 8 9 4 6 0

输入样例2：

10
3 1 2 8 7 5 9 4 0 6
1 3 2 8 5 7 4 9 0 6

输出样例2：

Merge Sort
1 2 3 8 4 5 7 9 0 6

思路：

通过插入排序判断是哪一种排序，然后进行对应排序的下一步。归并排序需要重新开始排序，判断归并到了哪一步。

题解：

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

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

bool check()
{
	for(int i = 1; i <= n; i++)
		if(a[i] != b[i])
			return false;
	return true;
}

int main()
{	
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for(int i = 1; i <= n; i++)
		scanf("%d", &b[i]);
	
	int p = 2;
	while(p <= n && b[p] >= b[p - 1])
		p++;
	int k = p;
	while(p <= n && a[p] == b[p])
		p++;
	if(p == n + 1)
	{
		printf("Insertion Sort\n");
		while(k > 1 && b[k] < b[k - 1])
		{
			swap(b[k], b[k - 1]);
			k--;
		}
		
		printf("%d", b[1]);
		for(int i = 2; i <= n; i++)
			printf(" %d", b[i]);
	}
	else
	{
		printf("Merge Sort\n");
		int k = 1;
		while(true)
		{
			bool match = check();
			
			int len = 1 << k;
			for(int i = 1; i <= n; i += len)
				sort(a + i, a + min(n + 1, i + len));
				
			if(match)
				break;
			k++;
		}
		
		printf("%d", a[1]);
		for(int i = 2; i <= n; i++)
			printf(" %d", a[i]);
	}

	return 0;
}