A1045 快速排序 (25分)

/*
题意：
1、找主元，就是左边比他小，右边比它都打就是主元了

解题：
1、答案说思路一样，怎么个一样法。我需要判断每一个数，左边是否都小于我，右边是否比我大，two points是根据两边i和j的规律，这算是打表，仔细体会B1040的打表
2、

learn && wrong:
1、左边记录最大值，右边记录最小值的写法不错
*/

#include <iostream>
#include <algorithm>
using namespace std; 

const int maxn = 100010;
const int INF = 0x3fffffff; //一个很大的数

//a为序列，leftmax和rightmin分别为每一位左边最大的数和右边最小的数
int a[maxn],leftmax[maxn],rightmin[maxn];

//ans记录所有主元，Num为主元个数

int ans[maxn],num = 0; 
int main(int argc, char** argv) {
    int n;
    cin>>n;//序列元素个数
    for(int i = 0;i < n;++i){
        scanf("%d",&a[i]);
    } 
    
    leftmax[0] = 0; //a[0]左边没有比它更大的数
    for(int i = 1;i < n;++i){
        leftmax[i] = max(leftmax[i - 1],a[i - 1]);  //由a[i - 1]推得i 
    } 
    
    rightmin[n - 1] = INF; //a[n - 1]右边没有比它更小的数 
    for(int i = n - 2;i >= 0;--i){
        rightmin[i] = min(rightmin[i + 1], a[i + 1]);  //由a[i + 1]推得a[i] 
    }
    
    for(int i = 0;i < n;++i){
        //左边所有数比它小，右边所有数比他大
        if(leftmax[i] < a[i] && rightmin[i] > a[i]){
            ans[num++] = a[i]; //记录主元 
        } 
    } 
    
    printf("%d\n",num); //主元个数
    for(int i = 0;i < num;++i){
        printf("%d", ans[i]);
        if(i != (num -1)) printf(" ");
    } 
    printf("\n");
    return 0;
}