题目链接：1045 快速排序

思路

正序找最大值，若一个数小于前方的最大值，则不是主位。再逆序找最小值，若一个数大于后方的最小值，则不是主位。综合两次遍历未被排除的即为主位。逆序查找同时，记录主位个数，用一个数组保存结果。主位从前往后必然是从小到大的，无需排序。注意点： a. 使用string保存结果，输出结果即使相同也会被判全错，所以还是要用int型数组保存结果。 b. 0主位第二行也要输出回车。

代码

#include <iostream> using namespace std; int main(){ int N; cin >> N; int max = 0; int a[N],M[N],out[N]; for(int i=0;i<N;i++){//正序输入并判最大 cin >> a[i]; if(a[i] > max){ max = a[i]; M[i] = 1;//入围主位待选 } else M[i] = 0;//退出待选 } int min = a[N-1]+1,count = 0; for(int i=N-1;i>=0;i--){//逆序判最小 if(a[i] < min) min = a[i]; else M[i] = 0; if(M[i]) out[count++] = a[i]; } cout << count << endl; for(int i=count-1;i>=0;i--){//倒序输出 cout << out[i]; if(i!=0) cout << ' '; } cout << endl; return 0; }