1098. Insertion or Heap Sort (25) 21'

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
//note:堆排序从1开始
void downAdjust(int low, int high){
    int i = 1, j = i * 2;
    while (j <= high) {
        if(j + 1 <= high && b[j] < b[j] + 1)
            j = j + 1;
        if (b[i] < b[j]) {
            swap(b[i], b[j]);
            i = j;
            j = i * 2;
        }else break;
    }
}

int main(){
    int n;
    cin >> n;
    a.resize(n+1);
    b.resize(n+1);
    for (int i = 1; i <= n; i++)  cin >> a[i];
    for (int i = 1; i <= n; i++)  cin >> b[i];
    int i, j;
    for (i = 1; i <= n - 1 && b[i] <= b[i+1]; i++);
    for (j = i + 1; a[j] == b[j] && j <= n; j++) ;
    if (j == n+1) {
        cout << "Insertion Sort" << endl;
        sort(b.begin() + 1, b.begin() + i + 2);
    }else{
        cout << "Heap Sort" << endl;
        j = n;
        while(j >= 2 && b[j] >= b[j - 1]) j--;
        swap(b[1], b[j]);
        downAdjust(1, j - 1);
    }
    for (int i = 1; i <= n; i++)
        printf("%d%c", b[i], i == n ? '\n' : ' ');
    return 0;
}