PAT 1089 Insert or Merge

港控/mmm° 2023-03-01 08:37 40阅读 0赞

7月PAT模拟考试中有这题，之前没真正做这题，考试的时候就没做出来。  
忽略了数组中有相等元素的情况，太坑了

#include <bits/stdc++.h>
    using namespace std;
    int origin[200],s[200];
    int n,idx;
    int merge(){ 
        int l,before=-1;
        for(l=1;;l*=2){ 
            int lun=n/l;
            for(int i=0;i<lun;i++){ 
                vector<int>vs,vs1;
                for(int j=l*i;j<l*(i+1)&&j<n;j++){ 
                    vs.push_back(s[j]);
                }
                if(!is_sorted(vs.begin(),vs.end())){ 
                    return l;
                }
            }
        }
    }
    int main(){ 
    #ifdef ONLINE_JUDGE
    #else
        freopen("../1.txt","r",stdin);
    #endif
        cin>>n;
        for(int i=0;i<n;++i){ 
            cin>>origin[i];
        }
        for(int i=0;i<n;++i){ 
            cin>>s[i];
        }
        for(idx=0;idx<n-1&&s[idx]<=s[idx+1];++idx){ }//不是<而是<=
        idx++;
        int insert=idx;
        for(;idx<n&&s[idx]==origin[idx];++idx){ 
        }
        //cout<<idx<<endl;
        if(idx==n){ 
            cout<<"Insertion Sort"<<endl;
            idx=insert;
            while (idx>=0){ 
                if(s[idx]<s[idx-1]){ 
                    swap(s[idx],s[idx-1]);
                }
                --idx;
            }
        } else{ 
            cout<<"Merge Sort"<<endl;
            int l=merge();
            for (int i = 0; i < n / l; i++)
                sort(s + i * l, s + (i + 1) * l);
            sort(s + n / l * l, s + n);
        }
        for(int i=0;i<n;++i){ 
            if(i!=0)cout<<" ";
            cout<<s[i];
        }
        return 0;
    }

要注意for(idx=0;idx<n-1&&s\[idx\]<=s\[idx+1\];++idx)\{\}//不是<而是<=  
否则就卡在了第四个点  
浙大数据结构的MOOC中特别讲了这题，昨天晚上刚看完但没做题，只知道思路，细节没注意就出错了。