PAT 1045 快速排序

1045 快速排序（25 分）

著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定 N=5$N=5$, 排列是1、3、2、4、5。则：
1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 N（≤105$\le {10}^5$）； 第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 109${10}^9$。
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：

5
1 3 2 4 5

输出样例：

3
1 4 5

解析

这题一看就知道暴力不能解决问题。所以要用空间换时间。
我是这样做的：

struct yes{
    int num;
    bool f1,f2;
};

定义一个struct结构体：f1表示该数是左边最大。f2表示该数是右边最大。
然后首先正着遍历一遍序列。并存储当前的最大值。如果当时在遍历的数小于这个最大值，就证明它不是主元。令f1=false。否则把该值设为最大值。
同理：逆序遍历一遍序列。并存储当前最小值。如果当时在遍历的数大于这个最小值。就证明它不是主元，令f2=false。否则把该值设为最小值。
最后：遍历一遍序列：如果f1,f2都是true，代表是主元


这题：测试点2我格式错误。看了别人的blog。原来是当没有可能的主元时，要输出(坑爹)

0
'\n'

Code:

#include<bits/stdc++.h>
using namespace std;
struct yes{
    int num;
    bool f1,f2;
};
int main()
{
    int N;
    cin>>N;
    vector<yes> data(N);
    for(int i=0;i<N;i++){
        cin>>data[i].num;
        data[i].f1=data[i].f2=true;
    }
    int min=data[N-1].num,max=data[0].num;
    for(int i=1;i<N;i++){
        if(data[i].num<max)
            data[i].f1=false;
        else
            max=data[i].num;
    }
    for(int i=N-2;i>=0;i--){
        if(data[i].num>min)
            data[i].f2=false;
        else
            min=data[i].num;
    }
    vector<int> result;
    for(int i=0;i<N;i++){
        if(data[i].f1==true && data[i].f1==data[i].f2)
            result.push_back(data[i].num);
    }
    printf("%d\n",result.size());
    sort(result.begin(),result.end());
    for(auto it1=result.begin();it1!=result.end();it1++)
        printf("%d%c",*it1,it1+1==result.end()?'\n':' ');
    if(result.size()==0)
    printf("\n");
}