AcWing 1591. 快速排序
原题链接
简单
作者:
sy123
,
2021-01-06 23:43:25
,
所有人可见
,
阅读 445
#include<bits/stdc++.h>
using namespace std;
const int N=100010,INF=2e9;
int n;
int a[N],maxn[N],minn[N];
int main(){
cin>>n;
for(int i=1;i<=n;i++)scanf("%d",&a[i]);
for(int i=1;i<=n;i++) maxn[i]=max(maxn[i-1],a[i]);
minn[n+1]=INF;//避免边界判断
for(int i=n;i>0;i--) minn[i]=min(minn[i+1],a[i]);
vector<int>s;
for(int i=1;i<=n;i++){
if(a[i]>maxn[i-1]&&a[i]<minn[i+1]){
s.push_back(a[i]);
}
}
cout<<s.size()<<endl;
sort(s.begin(),s.end());
bool flag=false;
for(auto it:s){
if(flag==false){
cout<<it;
flag=true;
}
else cout<<' '<<it;
}
cout<<endl;
return 0;
}