AcWing 1579. 插入还是归并
原题链接
中等
作者:
麦克斯韦妖_7
,
2021-08-20 22:51:47
,
所有人可见
,
阅读 272
#include <iostream>
#include <algorithm>
using namespace std;
int a[110], b[110];
int n;
bool check(){
for(int i = 1; i <= n; i ++){
if(a[i] != b[i]) return false;
}
return true;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
}
for(int i = 1; i <= n; i ++){
cin >> b[i];
}
int k = 2;
while(b[k] >= b[k - 1]) k ++;
int p = k;
while(b[p] == a[p] && p <= n) p ++;
if(p == n + 1){ // 插入排序
puts("Insertion Sort");
while(b[k] < b[k - 1]) swap(b[k], b[k - 1]), k --;
for(int i = 1; i <= n; i ++){
cout << b[i] << ' ';
}
}else{ // 归并排序
puts("Merge Sort");
int k = 1;
while(1){ // ***从初始序列开始归并排序,直到与b相同,然后再进行一趟归并排序,输出***
bool match = check();
int len = 1 << k;
for(int i = 1; i <= n; i += len){
sort(a + i, a + min(n + 1, i + len));
}
if(match) break;
k ++;
}
for(int i = 1; i <= n; i ++){
cout << a[i] << ' ';
}
}
cout << endl;
return 0;
}