1035 插入与归并 (25分)

测试点2未通过

得分：24/25
判断插入还是归并：
输入n1，n2数组
从后往前找n1和n2第一个不同的元素i，排序n1前i个元素，与n2进行比较，如果一样就是插入排序，否则是归并排序。

代码

#include <iostream>
#include"stdlib.h"
#include <vector>
#include <string>
#include <cstdio>
//scanf printf防止超时
#include <algorithm>
//vector的sort
#include <sstream>
//转换
using namespace std;

#include<iomanip>
//精度

#include<cmath>
//round四舍五入取整

bool judge(vector<int> n1,vector<int> n2)
{
    int index;
    for(int i=n1.size()-1;i>0;i--)
    {
        if(n1[i-1]!=n2[i-1]&&n1[i]==n2[i])
        {
            index=i;
            break;
        }
    }
    //cout<<index<<endl;
    sort(n1.begin(),n1.begin()+index);
    bool flag=true;
    for(int i=0;i<n1.size();i++)
    {
        if(n1[i]!=n2[i])
        {
            flag=false;
            break;
        }
    }
    return flag;
}
int main()
{
    int num;
    vector<int> n1,n2;
    cin>>num;
    for(int i=0;i<num;i++)
    {
        int temp;
        cin>>temp;
        n1.push_back(temp);
    }
    for(int i=0;i<num;i++)
    {
        int temp;
        cin>>temp;
        n2.push_back(temp);
    }
    bool flag=judge(n1,n2);

    if(!flag)
    {
        //merge
        cout<<"Merge Sort"<<endl;
        int temp=4;
        while(temp<num)
        {
            int t=num/temp;
            bool f=true;
            for(int i=0;i<t;i++)
            {
                for(int j=i*temp+1;j<(i+1)*temp;j++)
                {
                    if(n2[j-1]>n2[j])
                    {
                        f=false;
                        break;
                    }
                }

            }
            if(!f)
                {
                    break;
                }
            temp*=2;
        }
        //cout<<temp<<endl;
        if(temp>num)
        {
            sort(n2.begin(),n2.end());
        }
        else{
            int t=num/temp;

            for(int i=0;i<t;i++)
            {
                sort(n2.begin()+i*temp, n2.begin()+(i+1)*temp);
            }
            if(num%temp>0)
            {
                sort(n2.begin()+t*temp,n2.end());
            }

        }
        for(int i=0;i<n2.size()-1;i++)
        {
            cout<<n2[i]<<" ";
        }
        cout<<n2[n2.size()-1]<<endl;
    }else{
        cout<<"Insertion Sort"<<endl;

        int index;
        for(int i=n1.size()-1;i>0;i--)
        {
            if(n1[i-1]!=n2[i-1]&&n1[i]==n2[i])
            {
                index=i;
                break;
            }
        }
        //cout<<index<<endl;
        if(index+1<num)
        {
            if(n1[index+1]==n2[index+1])
                index++;
        }
        sort(n2.begin(),n2.begin()+index+1);

        
        for(int i=0;i<n2.size()-1;i++)
        {
            cout<<n2[i]<<" ";
        }
        cout<<n2[n2.size()-1]<<endl;
    }
    return 0;
}

PAT(Basic Level) Practice : 1035 插入与归并 (25分)

原文：https://www.cnblogs.com/zchq/p/13726300.html