著名的快速排序算法里有一个经典的划分过程：我们通常采用某种方法取一个元素作为主元，通过交换，把比主元小的元素放到它的左边，比主元大的元素放到它的右边。 给定划分后的 N 个互不相同的正整数的排列，请问有多少个元素可能是划分前选取的主元？
例如给定 $N = 5$, 排列是1、3、2、4、5。则：
- 1 的左边没有元素，右边的元素都比它大，所以它可能是主元；
- 尽管 3 的左边元素都比它小，但其右边的 2 比它小，所以它不能是主元；
- 尽管 2 的右边元素都比它大，但其左边的 3 比它大，所以它不能是主元；
- 类似原因，4 和 5 都可能是主元。
因此，有 3 个元素可能是主元。
输入格式：
输入在第 1 行中给出一个正整数 N（≤10?5??）； 第 2 行是空格分隔的 N 个不同的正整数，每个数不超过 10?9??。
输出格式：
在第 1 行中输出有可能是主元的元素个数；在第 2 行中按递增顺序输出这些元素，其间以 1 个空格分隔，行首尾不得有多余空格。
输入样例：
5
1 3 2 4 5
输出样例：
3
1 4 5就算第二行没有数，也要输出个回车
#include<iostream>
#include<algorithm>using namespace std;
const int maxn=1e5+10;int ans[maxn];
int a[maxn];
int b[maxn];
//快排选择的主元 在排序后其位置不会再发生变化
//所以一个元素如果被选为主元，则 在排序后其位置不会再发生变化
int main(){int n;cin>>n;for(int i=0;i<n;i++){cin>>a[i];b[i]=a[i];}sort(a,a+n);int big=0,num=0;for(int i=0;i<n;i++){if( a[i] == b[i] && big < b[i] ) ans[num++]=a[i];big = max(big,b[i]);}cout<<num<<endl;if(num){//可能引发段错误，非法内存 cout<<ans[0]; for(int i=1;i<num;i++) cout<<" "<<ans[i]; }cout<<endl;return 0;
}
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>using namespace std;
const int maxn=1e5+10;
const int N=10;
const int INF = 0x3fff;int a[maxn];
int ans[maxn];
int leftMax[maxn];
int rightMin[maxn];
//暴力破会超时，这里要想到用大小间的继承关系
int main(){int n;cin>>n;for(int i=0;i<n;i++) cin>>a[i];leftMax[0]=a[0];for(int i=1;i<n;i++)leftMax[i] = max(a[i],leftMax[i-1]);rightMin[n-1] = a[n-1];for(int i=n-2;i>=0;i--)rightMin[i] = min(a[i],rightMin[i+1]);int cnt=0;for(int i=0;i<n;i++){int f=0;if( i==0 ) {if(a[i] < rightMin[i+1] ) f=1;}else if (i==n-1){if( leftMax[i-1] < a[i]) f=1;}else if(a[i] > leftMax[i-1] && a[i] < rightMin[i+1]){f=1; }//左边的都比它小，右边的都比它大则隐含着从小到大的排序 if(f) ans[cnt++] = a[i];}cout<<cnt<<endl;if(cnt) {cout<<ans[0];for(int i=1;i<cnt;i++)cout<<" "<<ans[i];}cout<<endl;return 0;
}
time limited error：
超时原因：每次判断一个数是否是主元的时候都需要对数组进行遍历。考虑如何才能不每次判断的时候都遍历数组十分重要
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<string>
#include<vector>
using namespace std;
const int maxn=1e5+10;
const int N=10;int a[maxn];
int b[maxn];
vector<int> v;int main(){int n;cin>>n;for(int i=0;i<n;i++) {cin>>a[i];b[i]=a[i];}//对于快排来说，选定的主元在排序前后位置就不会再发生变化//这是个充分不必要条件 sort(a,a+n);for(int k=0;k<n;k++){if(a[k] == b[k]){int x=a[k];int i=k,j=k;超时 do i--; while(i>=0 && b[i]<x) ; if(i>=0) continue;do j++; while(j<n && b[j]>x) ; if(j<n) continue;if( i<0 && j>=n ) v.push_back(x);}}cout<<v.size()<<endl;if(v.size()){sort(v.begin(),v.end());cout<<v[0];for(int i=1;i<v.size();i++) cout<<" "<<v[i];}cout<<endl;return 0;
}