[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

注意!此信息未认证,请谨慎判断信息的真实性!

全部评论
空

相关内容推荐

头像
点赞 评论 收藏
转发
头像 头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
头像
点赞 评论 收藏
转发
点赞 收藏 评论
分享

全站热榜

正在热议