2019-08-09 （甲级1题）

1101 Quick Sort (25 分)

这道题大致意思就是要你找到那些左边元素都比它小，右边元素都比它大的元素，然后统计个数并增序输出。
这题有个坑： 当统计个数为0时，你要输出两个连续的换行符\n才能过测试点2。
代码如下：

#include <iostream>
using namespace std;

int main(){
    int n,maxn=0,cnt=0,minn;
    cin>>n;
    int *a=new int[n]();
    int *b=new int[n]();
    int *c=new int[n]();
    for(int i=0;i<n;i++){
        cin>>a[i];
        b[i]=0;
        c[i]=0;
    }
    for(int i=0;i<n;i++){
        //如果第i个比之前最大的大，那b里记录它，并将maxn赋值
        if(a[i]>=maxn){
            b[i]=1;
            maxn=a[i];
        }
    }
    minn=maxn;
    for(int i=n-1;i>=0;i--){
        //如果第i个比之后最小的小，在c里记录它，并将minn赋值
        if(a[i]<=minn){
            c[i]=1;
            minn=a[i];
        }
    }
    for(int i=0;i<n;i++){
        if(b[i]==1&&c[i]==1)cnt++;
    }
    if(cnt>0)cout<<cnt<<endl;
    else{
        cout<<cnt<<endl;
        cout<<endl;
        return 0;
    }
    int flag=0;
    for(int i=0;i<n;i++){
        if(b[i]==1&&c[i]==1){
            if(flag>0)cout<<" ";
            cout<<a[i];
            flag++;
        }
    }
    return 0;
}