[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
查看14道真题和解析