AcWing 1591. 快速排序
原题链接
简单
作者:
在月球_0
,
2024-10-10 16:34:07
,
所有人可见
,
阅读 2
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10,INF = 1e9 + 10;
int a[N],l[N],r[N];
int n;
int main()
{
cin >> n;
for(int i = 1;i <= n;i++)
{
cin >> a[i];
}
//预处理两个数组
for(int i = 1;i <= n;i++) l[i] = max(l[i - 1],a[i]);
r[n + 1] = INF;
for(int i = n;i > 0;i--) r[i] = min(r[i + 1],a[i]);
vector<int> ret;
for(int i = 1;i < n + 1;i++)
{
if(a[i] > l[i - 1] && a[i] < r[i + 1])
{
ret.push_back(a[i]);
}
}
cout << ret.size() << endl;
if(ret.size() == 0) {
cout << endl;
}else {
cout << ret[0];
for(int i = 1;i < ret.size();i++) cout << " " << ret[i];
}
return 0;
}