1101 Quick Sort（二刷）

 1 #include<iostream>
 2 #include<algorithm>
 3 using namespace std;
 4  
 5 const int INF = 0x3fffffff;
 6 //当前位置的元素必须满足，大于等于左边的最大元素，小于等于右边的最小元素，才可能是主元
 7 int a[100010] = {0};
 8 int leftMAX[100010] = {0};
 9 int rightMIN[100010] = {0};
10 int ans[100010] = {0},num = 0;
11 int main() {
12     int n,cnt = 0;
13     scanf("%d",&n);
14     for(int i = 1; i <= n; ++i)
15         scanf("%d",&a[i]);
16     rightMIN[n+1] = INF;
17     for(int i = 1; i <=n; ++i)
18         leftMAX[i] = max(leftMAX[i-1],a[i]);
19     for(int i = n; i>=1; --i)
20         rightMIN[i] = min(rightMIN[i+1],a[i]);
21     for(int i = 1; i <= n; ++i) {
22         if(a[i] >= leftMAX[i] && a[i] <= rightMIN[i]) {
23             cnt++;
24             ans[num++] = a[i];
25         }
26     }
27     printf("%d\n",cnt);
28     for(int i = 0; i < num; ++i) {
29         if(i > 0) printf(" ");
30         printf("%d",ans[i]);
31     }
32     printf("\n");//不加这句，测试点2无法通过
33     return 0;
34 }