PAT甲级1089.

目录

A1089

题目

样例

样例1

输入:

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

输出:

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

输出:

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

思路和坑点

　　根据插入排序和归并排序的特点，插入排序前一部分有序，后一部分和原序列相同。一旦排除插入排序，则是归并排序，对原始序列模拟归并排序，当和中间序列相同时再进行一次归并几位所求结果。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,i,j;
    cin>>n;
    vector<int> v(n),vs(n);                 //两个序列，v为原始序列，vs为中间序列 
    for(i=0;i<n;i++)    cin>>v[i];
    for(i=0;i<n;i++)    cin>>vs[i];
    for(i=0;i<n-1;i++){                     //找vs中前边不是有序的位置 
        if(vs[i]>vs[i+1]){
            j=i+1; break;
        }
    }
    for(j;j<n;j++){                         //后半部分如果还和原始序列相同，则是插入 ，否则是归并 
        if(v[j]!=vs[j]) break;
    }
    if(j==n){                               //如果后半部分和原始序列相同，j会走到n 
        puts("Insertion Sort");
        sort(v.begin(),v.begin()+i+2);      //将前半部分排序，统一都在v上操作，这样最后序列输出可以统一 
    } 
    else{                    
        puts("Merge Sort");
        int  step=2,flag=1;                 //step表示归并段的长度，初始化为2，flag表示是否到达中间序列 
        while(flag){
            if(v==vs) flag=0;               //如果归并到给定的中间结果，修改flag=0，然后再归并一次之后结束循环 
            for(i=0;i<n/step;i++)           //整齐部分的归并段排序，每个段内使用快排 
                sort(v.begin()+i*step,v.begin()+(i+1)*step);
            sort(v.begin()+i*step,v.end()); //结尾部分不够整个step的单独处理 
            step*=2;                        //归并步长加倍 
        }
    } 
    for(int i=0;i<n;i++){                   //输出结果 
        if(i) putchar(' ');
        printf("%d",v[i]);
    }
    return 0;
}