PAT甲级1098.

目录

A1098

题目

样例

样例1

输入:

10
3 1 2 8 7 5 9 4 6 0
1 2 3 7 8 5 9 4 6 0

输出:

Insertion Sort
1 2 3 5 7 8 9 4 6 0

样例2

输入:

10
3 1 2 8 7 5 9 4 6 0
6 4 5 1 0 3 2 7 8 9

输出:

Heap Sort
5 4 3 1 0 2 6 7 8 9

思路和坑点

　　利用插入排序的特征，前半部分有序，后半部分和原序列相同的特性。辨别是不是插入排序，如果是则在插入一个元素，否则是堆排序，可以直接利用c++11标准中的heap的相关操作，找到不满足堆的位置，然后将前边满足堆的部分弹出堆顶元素到尾巴上。heap的操作可以参考PAT总结那篇博客中的总结，也可以手动写函数实现。

AC代码

#include<bits/stdc++.h>
using namespace std;
int main(void){
#ifdef ONLINE_JUDGE
#else
    freopen("1.txt","r",stdin);
#endif
    int n,i=0,j;
    cin>>n;
    vector<int> v(n),mid(n);            //存放原始序列和中间序列 
    for(i=0;i<n;i++)                    //读入数据 
        scanf("%d",&v[i]);
    for(i=0;i<n;i++)
        scanf("%d",&mid[i]);
    for(i=0;i<n-1;i++){                 //从中间序列开始，找到第一个不符合递增序列的下标j 
        if(mid[i]>mid[i+1]){
            j=i+1;
            i++;break;
        }
    }
    for(j;j<n;j++)                      //从j开始，往后比较原始序列和中间序列 
        if(v[j]!=mid[j]) break;
    if(j==n){                           //如果后半部分和原始序列相同，则为插入排序 
        puts("Insertion Sort");
        sort(mid.begin(),mid.begin()+i+1);
    }
    else{
        puts("Heap Sort");              //否则为堆排序 
        auto pos=is_heap_until(mid.begin(),mid.end(),less<int>());
        pop_heap(mid.begin(),pos);      //查找第一个不满足堆的位置（大根堆），然后将前半部分的堆pop操作 
    }
    for(int i=0;i<n;i++){               //输出结果 
        if(i) putchar(' ');
        printf("%d",mid[i]);
    }
    return 0;
}