PAT A1089 Insert or Merge

题目链接

解题思路

使用vector来保存数字序列，方便直接比较！然后分别模拟插入排序和归并排序的过程，使用sort函数帮助实现，如果满足等于第二个序列，就退出，并记录当前状态，方便进一步打印下一次迭代。

注意

1、sort取不到右边界，所以要加一。

2、归并排序的步数for循环，要使用step/2<n进行判断，因为如果n等于10，用step<n来判断的话，step等于8就结束循环了，step=16无法进入循环，最后一次归并排序没有完成。

3、还有就是注意插入和归并排序两个函数在等于的时候退出，此时状态还是保留在当前状态，如果要打印下一步迭代，需要先进行inp++和step*=2的将其状态设置到下一步。

代码

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int n,inp=1,step=2;
vector<int> temp,init_seq,part_seq;

void printArr(vector<int> v){
    for(int i=0;i<v.size();i++){
        if(i!=0) printf(" ");
        printf("%d",v[i]);
    }

}
bool insert_sort(){
    bool flag=false;
    for(inp=1;inp<init_seq.size();inp++){
        sort(init_seq.begin(),init_seq.begin()+inp+1);//sort function can't get the right boundary
        if (init_seq==part_seq) {
            flag=true;
            break;
        }
    }
    return flag;
}

bool merge_sort(){
    bool flag=false;
    for(step=2;step/2<n;step*=2){
        for(int i=0;i<n;i+=step){
            //if the number of final group less than step,use n as the upper bound
            sort(init_seq.begin()+i,init_seq.begin()+min(i+step,n));
        }
        if (init_seq==part_seq) {
            flag=true;
            break;
        }
    }
    return flag;
}

int main(){
    scanf("%d",&n);
    int x;
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        init_seq.push_back(x);
    }
    for(int i=0;i<n;i++) {
        scanf("%d",&x);
        part_seq.push_back(x);
    }
    temp=init_seq;
    bool isinsert=false,ismerge=false;
    isinsert=insert_sort();
    if (isinsert){
        inp++;
        printf("Insertion Sort\n");
        sort(init_seq.begin(),init_seq.begin()+inp+1);
        printArr(init_seq);
    }
    init_seq=temp;
    ismerge=merge_sort();
    if (ismerge){
        printf("Merge Sort\n");
        step*=2;
        for(int i=0;i<n;i+=step){
            sort(init_seq.begin()+i,init_seq.begin()+min(i+step,n));
        }
        printArr(init_seq);
    }
    return 0;
}