[PAT解题报告] Insert or Merge

给定一个整数数组，问当前的撞状态是插入排序造成的还是归并排序造成的。

题目给定了插入排序和归并排序的过程，特点如下：

（1）插入排序，每次一定是前m项有序。

（2）归并排序，每次一定是长度为2^k的段有序。

因为n不大（才100），所以我没有真正模拟这两个排序过程。

对于插入排序，我每次调用sort(c, c + m)

对于归并，我每段单独调用sort，注意长度可能有尾巴。

直接暴力排序比较就好了。

注意点：不是找到第一个相同步骤就行了，而是应该找到第一个不同的步骤，因为有时候可能目前这个状态能在某种排序下面持续不变，例如插入排序时，输入数组前m项已经排好顺序了，我们可以需要找到第一个不一样的序列，换句话说，输出和输入必须时不同的。

代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
using namespace std;

int a[105], b[105], c[105];


void print(int *a,int n) {
        for (int i = 0; i < n; ++i) {
                if (i) {
                        putchar(' ');
                }
                printf("%d",a[i]);
        }
        puts("");
}

bool same(int *a,int *b,int n) {
        for (int i = 0; i < n; ++i) {
                if (a[i] != b[i]) {
                        return false;
                }
        }
        return true;
}

bool insertion(int *c, int n) {
bool mark = false;
        for (int i = 2; i <= n; ++i) {
        sort(c, c + i);
                if (same(c, b, n)) {
                        mark = true;
                }
        if (mark && (!same(c, b, n))) {
            puts("Insertion Sort");
            print(c, n);
            return true;
        }

        }
        return false;

}



bool merge(int *c,int n) {
bool mark = false;
        for (int i = 2; i <= n; i <<= 1) {
            int j;
                for (j = 0; j + i <= n; j += i) {
                    sort(c + j, c + j + i);
                }
                sort(c + j, c + n);
                if (same(c, b, n)) {
                        mark = true;
                }
            if (mark && (!same(c, b, n))) {
                    puts("Merge Sort");
                    print(c, n);
                    return true;
            }
        
        }
        return false;
}


int main() {
int n;
        scanf("%d",&n);
        for (int i = 0; i < n; ++i) {
                scanf("%d",a + i);
        }
        for (int i = 0; i < n; ++i) {
                scanf("%d", b + i);
        }
        memcpy(c, a, sizeof(a));
        if (!insertion(c, n)) {
                merge(a, n);
        }
        return 0;
}

原题链接： http://www.patest.cn/contests/pat-a-practise/1089

全部评论

推荐最新楼层

北海3192

叠纸游戏_Unity开发

#include<cstdio> #include<algorithm> using namespace std; const int maxn = 110; int origin[maxn], tempOri[maxn], changed[maxn]; int n; bool isSame(int a[], int b[]){ for(int i = 0; i < n; i++){ if(a[i] != b[i]) return false; } return true; } void showArray(int a[]){ for(int i = 0; i < n; i++){ printf("%d",a[i]); if(i < n-1) printf(" "); } } bool insertSort(){ bool flag = false; for(int i = 1; i < n; i++){ if(i != 1 && isSame(tempOri, changed)){ flag = true; } int temp = tempOri[i], j = i; while(j > 0 && tempOri[j - 1] > temp){ tempOri[j] = tempOri[j - 1]; j--; } tempOri[j] = temp; if(flag && !isSame(tempOri, changed)) return true; } return false; } void mergeSort(){ bool flag = false; for(int step = 2; step / 2 <= n; step *= 2){ if(step != 2 && isSame(tempOri, changed)){ flag =true; } for(int i = 0; i < n; i += step){ sort(tempOri + i, tempOri + min(step + i, n)); } if(flag){ showArray(tempOri); return; } } } int main(){ scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%d", &origin[i]); tempOri[i] = origin[i]; } for(int i = 0; i < n; i++){ scanf("%d", &changed[i]); } if(insertSort()){ printf("Insertion Sort\n"); showArray(tempOri); }else{ printf("Merge Sort\n"); for(int i = 0; i < n; i++){ tempOri[i] = origin[i]; } mergeSort(); } return 0; }

点赞回复分享

发布于 2017-02-15 23:55