【PAT甲级 - C++题解】1089 Insert or Merge

1089 Insert or Merge

According to Wikipedia:

Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there. It repeats until no input elements remain.

Merge sort works as follows: Divide the unsorted list into N sublists, each containing 1 element (a list of 1 element is considered sorted). Then repeatedly merge two adjacent sublists to produce new sorted sublists until there is only 1 sublist remaining.

Now given the initial sequence of integers, together with a sequence which is a result of several iterations of some sorting method, can you tell which sorting method we are using?

Input Specification:

Each input file contains one test case. For each case, the first line gives a positive integer N (≤100). Then in the next line, N integers are given as the initial sequence. The last line contains the partially sorted sequence of the N numbers. It is assumed that the target sequence is always ascending. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in the first line either “Insertion Sort” or “Merge Sort” to indicate the method used to obtain the partial result. Then run this method for one more iteration and output in the second line the resuling sequence. It is guaranteed that the answer is unique for each test case. All the numbers in a line must be separated by a space, and there must be no extra space at the end of the line.

Sample Input 1:

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

Sample Output 1:

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

Sample Input 2:

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

Sample Output 2:

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

题意

根据维基百科：

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

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

现在给定两个数组，第一个数组是初始数组，第二个数组是已经进行过排序的数组，但是还没有排完序，需要我们去判断这个还没排完序的数组它是用了插入排序还是归并排序的方法。

然后输出对应的排序方法，并用该排序方法再往后进行一次迭代，并输出。

思路

这和 1098 那道题十分相似，这题可以按照那题思路，先判断是否为插入排序，因为插入排序的数组中前面是有序的，后面是无序的，并且后面没有排序的地方和原数组同一位置是相等的，基于这个性质我们可以判断是否为插入排序。

而归并排序我们需要从头开始比较，即拿原数组 a 开始归并排序的迭代，直到迭代的数组与 b 相同，则说明原数组排序到了这里，然后再进行一次迭代并输出即可。

具体思路如下：

输入两个数组 a 和 b 。

不管三七二十一，我都先把数组 b 当做前面是有序的，然后找到数组中从前往后哪个地方开始是无序的。然后用 k 保存该位置，再继续往后对比 b 数组中 k 以后的元素是否与 a 数组中 k 以后的元素都相同，因为如果是插入排序，每次迭代都只会往后取一位元素跟前面排好序的元素进行对比，其后面的元素是没被动过的；而归并排序整个数组元素都会发生变化。

判断是哪个排序，然后进行对于排序的下一次迭代操作。

输出迭代后的数组。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int a[N], b[N];
int n;
//判断a和b数组元素是否想等
bool check()
{
    for (int i = 0; i < n; i++)
        if (a[i] != b[i])
            return false;
    return true;
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)    cin >> a[i];
    for (int i = 0; i < n; i++)    cin >> b[i];
    int p = 1;
    while (b[p] >= b[p - 1]) p++;
    int k = p;
    while (p < n && a[p] == b[p])  p++;
    if (p == n)    //如果是插入排序
    {
        cout << "Insertion Sort" << endl;
        sort(b, b + k + 1);
        cout << b[0];
        for (int i = 1; i < n; i++)    cout << " " << b[i];
        cout << endl;
    }
    else    //如果是归并排序
    {
        cout << "Merge Sort" << endl;
        k = 1;
        while (1)
        {
            bool match = check();
            //无论如何都先进行一次迭代
            int len = 1 << k;
            for (int i = 0; i < n; i += len)
                sort(a + i, a + min(n, i + len));
            if (match)  break;
            k++;
        }
        cout << a[0];
        for (int i = 1; i < n; i++)    cout << " " << a[i];
        cout << endl;
    }
    return 0;
}