題目鏈接：點擊查看

題目大意：給出兩列數字，問第二列數是由第一列數怎樣排序得到的，題目保證答案唯一，并且只有歸并排序或插入排序兩種選擇

題目分析：因為一開始不太了解歸并排序和插入排序的特點，所以有點無從下手，去網上看了一下各自的特點后，就有了模擬的大致方向了，先在這里掛一下兩種排序中間過程的特點：（針對這個題目而言）

插入排序： 前面的一段連續序列有序，后面剩下的序列與原序列一一對應

歸并排序：設當前歸并長度為len(len為2的冪次，最小為1)，則每長度為len的區間內都保證有序

有了這個特點，再加上題目保證了除了歸并排序就是插入排序，因為插入排序的特點看起來比較好判斷，那么我們可以先判斷一下該序列是否是插入排序的中間過程，若是的話，記錄一下斷點，從頭到斷點后的一個位置sort一下答案就出來了；若不是插入排序，那么就只能是歸并排序了，我們可以先找出當前歸并排序的歸并長度len，將len乘二后模擬一遍歸并排序的規則即可（即每個長度為len的區間都單獨排序）

這里有幾個細節需要注意一下，我也不知道算不算坑點：

題目只是說了要保證升序排序，但沒保證是嚴格升序，雖然兩個樣例都給出的是嚴格升序，但是我們在判斷的時候都要以非嚴格升序來判斷，不然會有一組測試點過不去

在處理歸并排序時，若數組長度n無法整除歸并長度len，也就是說明最后肯定會剩下一段區間比len要小，這個需要單獨排序

在獲得歸并長度len后，我們需要將其乘2后再進行新一輪的排序，此時需要注意一下，若len*2>n的情況下，我們只需要處理到n即可

代碼：（自認為還是寫的比較清晰易看的）

#include<iostream> #include<cstdlib> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=110;int n;int a[N],b[N];int check()//判斷是否為插入排序 {b[0]=INT_MIN;int i;for(i=1;i<=n;i++){if(b[i-1]>b[i])break;}int mark=i;for(;i<=n;i++)if(a[i]!=b[i])return 0;return mark; }int getlen()//獲得歸并排序的長度 {for(int len=1;len<=n;len<<=1){for(int i=1;i+len-1<=n;i+=len){int j=i+len-1;for(int k=i+1;k<=j;k++)if(b[k]<=b[k-1])return len;}}return n;//如果前面的最大長度len都通過了，那么下一次歸并排序的長度最大到n結束 }void print() {printf("%d",b[1]);for(int i=2;i<=n;i++)printf(" %d",b[i]);printf("\n"); } int main() { // freopen("input.txt","r",stdin);scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",a+i);for(int i=1;i<=n;i++)scanf("%d",b+i);int mark=check();if(mark)//插入排序 {puts("Insertion Sort");sort(b+1,b+1+mark);}else//歸并排序 {puts("Merge Sort");int len=getlen();for(int i=1;i+len-1<=n;i+=len)//每長度為len的區間都單獨排序 sort(b+i,b+i+len);sort(b+n/len*len+1,b+1+n);//最后剩余的那段也記得排序 }print();return 0; }

?

總結

以上是生活随笔為你收集整理的PAT (Basic Level) 1035 插入与归并(模拟)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。