题目

时间限制
200 ms
内存限制
65536 kB
代码长度限制
8000 B
判题程序
Standard
作者
CHEN, Yue
根据维基百科的定义：
插入排序是迭代算法，逐一获得输入数据，逐步产生有序的输出序列。每步迭代中，算法从输入序列中取出一元素，将之插入有序序列中正确的位置。如此迭代直到全部元素有序。
归并排序进行如下迭代操作：首先将原始序列看成N个只包含1个元素的有序子序列，然后每次迭代归并两个相邻的有序子序列，直到最后只剩下1个有序的序列。
现给定原始序列和由某排序算法产生的中间序列，请你判断该算法究竟是哪种排序算法？
输入格式：
输入在第一行给出正整数N (<=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

分析：

还是模拟，可以拆解成两个步骤：
1.先区分插入与归并，
2.考虑实现排序的下一步
3.细节问题，比如归并后面剩下的比排序区间小怎么办?
对于问题1，插入前m个是升序排列，后面不变；归并是每w个升序。所以先找前面升序数组，当未升序时候，如果后面两数组全部一样，说明是插入排序，否则是归并排序。
对于问题2，当为插入排序的时候，只需要把未排序部分”拿”一个进来排序即可；当为归并排序时，模拟整个过程，当当前排序与b数组相同，再排序一轮输出。

代码(cpp)

#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int n,a[100+5],b[100+5];
    int flag=0;
    int k;
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<n;i++)
        cin>>b[i];
    for(int i=0;i<n-1;i++){
        if(!flag && b[i]>b[i+1]){
            flag=1;
            k=i+1; //后一个的坐标
            continue;
        }
        if(flag==1 && a[i]!=b[i])
            flag=2;
        if(i==n-2)
            if(flag==1 && a[i+1]!=b[i+1])
                flag=2;
    }
    if(flag==1){
        cout<<"Insertion Sort"<<endl;
        sort(b,b+k+1);  //后一个坐标的个数
        cout<<b[0];
        for(int i=1;i<n;i++)
            cout<<" "<<b[i];
    }
    else if(flag==2){
        cout<<"Merge Sort"<<endl;
        for(int i=1;i<=n;i*=2){
            int j;
            for(j=0;j<n-n%i;j+=i)
                sort(a+j,a+j+i);
            sort(a+n-n%i,a+n);
            for(j=0;j<n;j++)
                if(a[j]!=b[j])
                    break;
            if(j==n){
                i*=2;
                for(j=0;j<n-n%i;j+=i)
                    sort(a+j,a+j+i);
                sort(a+n-n%i,a+n);
                cout<<a[0];
                for(int l=1;l<n;l++)
                    cout<<" "<<a[l];
                break;
            }
        }
    }
    return 0;

}