AcWing 1588. 插入还是堆排序
原题链接
中等
作者:
fei0825
,
2023-05-31 17:31:57
,
所有人可见
,
阅读 117
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int a[N], b[N], sz, n;
int insert(){
int i=2;
while( i<=n && b[i-1]<=b[i] ) i++;
int j = i;
while( i<=n && a[i]==b[i] ) i++;
if( i==n+1 ) return j;
return -1;
}
void down(int u){
int l=u<<1, r=u<<1|1;
int t = u;
if( l<=sz && b[l]>b[t] ) t = l;
if( r<=sz && b[r]>b[t] ) t = r;
if( t!=u ){
swap(b[t], b[u]);
down(t);
}
}
void pop(){
swap(b[1], b[sz--]);
down(1);
}
int main(){
scanf("%d", &n);
for( int i=1; i<=n; i++ ) scanf("%d", &a[i]);
for( int i=1; i<=n; i++ ) scanf("%d", &b[i]);
int j = insert();
if( j>1 ){
puts("Insertion Sort");
for( int i=1; i<j; i++ ){
if( b[i]>b[j] ) swap(b[i], b[j]);
if( i>1 ) printf(" ");
printf("%d", b[i]);
}
while( j<=n ) printf(" %d", b[j++]);
puts("");
}
else{
puts("Heap Sort");
sz = n;
while( b[sz]>b[1] ) sz--;
pop();
for( int i=1; i<=n; i++ ){
if( i>1 ) printf(" ");
printf("%d", b[i]);
}
puts("");
}
return 0;
}