PAT--1035 插入与归并

题目描述

根据维基百科的定义：

插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。

归并排序进行如下迭代操作：首先将原始序列看成 $N$ 个只包含 $1$ 个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下 $1$ 个有序的序列。

现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？

输入格式：

输入在第一行给出正整数 $N(\le 100)$；随后一行给出原始序列的 $N$ 个整数；最后一行给出由某排序算法产生的中间序列。这里假设排序的目标序列是升序。数字间以空格分隔。

输出格式：

首先在第 $1$ 行中输出 Insertion Sort 表示插入排序、或 Merge Sort 表示归并排序；然后在第 $2$ 行中输出用该排序算法再迭代一轮的结果序列。题目保证每组测试的结果是唯一的。数字间以空格分隔，且行首尾不得有多余空格。

输入样例 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

解析

• 插入排序。最前面若干个数保证有序，后续部分保持原样，因此我们就可以遍历一次，找出第一个逆序的位置，记为 $pos$，那么我们就比较一下 $a,b$ 数组对于 $[pos,n]$ 这个区间内是否相同，如果相同，那么就说明是插入排序。
• 归并排序。第一次每两个一组，内部排序，第二次四个一组，内部排序，以此类推。因此我们可以枚举 $2,4,8,...$，对 $a$ 数组进行排序，直到某一次，发现排完序之后 $a$ 数组和 $b$ 数组相同了，假设当前每一组的元素个数为 $i$，那么我们下一步就是要将每 $i\ast 2$ 个元素为一组进行排序，再排序一次即可。

代码实现

#include <bits/stdc++.h>
using namespace std;
const int N = 105;
int a[N], b[N];
void solve() {int n;cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];for (int i = 1; i <= n; i++) cin >> b[i];int pos = -1;for (int i = 2; i <= n; i++) {if (b[i] < b[i - 1]) {pos = i;//找到第一个逆序的位置break;}}bool ok = true;//判断是否是插入排序for (int i = pos; i <= n; i++) if (a[i] != b[i]) ok = false;if (ok) {cout << "Insertion Sort\n";sort(a + 1, a + pos + 1);//下一步就是把[1,pos]排好序for (int i = 1; i <= n; i++) {if (i != 1) printf(" ");cout << a[i];}} else {cout << "Merge Sort\n";for (int i = 2; i <= n; i *= 2) {//枚举当前排序块的长度for (int l = 1; l <= n; l += i) sort(a + l, a + min(n, l + i - 1) + 1);bool ok = true;//判断是否到达题目给定的状态for (int k = 1; k <= n; k++) if (a[k] != b[k]) ok = false;//判断是否相同了if (ok) {//如果到达,直接模拟下一步即可i *= 2;for (int l = 1; l <= n; l += i) sort(a + l, a + min(n, l + i - 1) + 1);for (int j = 1; j <= n; j++) {if (j != 1) cout << " ";cout << a[j];}return;}}}
}
int main()
{int t = 1;//cin>>t;while (t--) solve();return 0;
}