*B1035 插入与归并/A1089 Insert or Merge

题目：https://pintia.cn/problem-sets/994805260223102976/problems/994805286714327040

注意点

1. 说难不难说简单不简单，不光考察了插入和归并排序，主要是循环的设置和函数返回
2. 初试序列不能参与比较
3. 注意一下归并排序的步长问题

for(int step = 2; step / 2 < n; step *= 2){
    if(step != 2 && isSame(temp_list,list2)) flag = true;
    for(int i = 0; i < n; i += step) sort(temp_list.begin() + i, temp_list.begin() + min(i + step, n));
}

代码

#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
vector<int> list1, temp_list,list2;
int n;
bool isSame(vector<int> A, vector<int> B){
    int len = max(A.size(),B.size());
    for(int i = 0; i < len; i++){
        if(A[i] != B[i]) return false;
    }
    return true;
}
void showArr(vector<int> A){
    int len = A.size();
    for(int i = 0; i < len; i++){
        printf("%d",A[i]);
        if(i != len-1) printf(" ");
    }
    printf("\n");
}
bool Insertion_Sort(){
    bool flag = false;
    for(int i = 1; i < n; i++){
        if(i!=1&&isSame(temp_list,list2)) flag = true;
        int min = i;
        while(min>=1&&temp_list[min-1]>temp_list[min]){
            swap(temp_list[min-1],temp_list[min]);
            min--;
        }
        if(flag) return true;
    }
    return false;
}
void Merge_Sort(){
    bool flag = false;
    for(int step = 2; step / 2 < n; step *= 2){
        if(step != 2 && isSame(temp_list,list2)) flag = true;
        for(int i = 0; i < n; i += step) sort(temp_list.begin() + i, temp_list.begin() + min(i + step, n));
        if(flag){
            showArr(temp_list);
            return;
        }
    }
}
int main(){
    scanf("%d",&n);
    list1.resize(n),list2.resize(n);
    for(int i = 0; i < n; i++) scanf("%d",&list1[i]);
    temp_list = list1;
    for(int i = 0; i < n; i++) scanf("%d",&list2[i]);
    if(Insertion_Sort()){
        printf("Insertion Sort\n");
        showArr(temp_list);
    }
    else{
        temp_list = list1;
        printf("Merge Sort\n");
        Merge_Sort();
    }
}