AcWing 1579. 插入还是归并
原题链接
中等
作者:
mkuiwu
,
2021-01-19 23:06:24
,
所有人可见
,
阅读 420
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;
const int N = 110;
// 来两个数组来接受输入数据
int a[N], b[N];
int n;
bool is_macth() {
for (int i = 0; i < n; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) cin >> b[i];
bool isIns = true;
int k = 0;
// 找到的是 最后匹配的位置
while (k + 1 < n && b[k + 1] >= b[k]) k++;
int cur = k + 1; // k 的后一个位置开始
while (cur < n) {
if (a[cur] != b[cur]) isIns = false;
cur++;
}
if (isIns) {// 是插入排序
puts("Insertion Sort");
// 对b 进行下一波排序, + 1 是 原数组 再加一 就是 下一轮
sort(b, b + k + 1 + 1);
cout << b[0];
for (int i = 1; i < n; i++)
cout << ' ' << b[i];
cout << endl;
}
else { // 是归并排序的情况下
puts("Merge Sort");
// 设计一个函数来判断一下, 如果不保证有解就会爆炸
int k = 0, len;
while (true) {
// 多做了一次, 写在这个位置的话
auto match = is_macth();
len = 1 << k;
// 模拟
for (int i = 0; i < n; i += len) {
sort(a + i, a + min(n, len + i));
}
if (match) break;
k++;
}
cout << a[0];
for (int i = 1; i < n; i++)
cout << ' ' << a[i];
cout << endl;
}
return 0;
}