题目链接：1045 快速排序 (25分)
题目
解题思路
这个题有点动态规划的意思。
主元的意思就是，这个数的左边全是小于它的数，右边全是大于它的数。这样在快排的时候它就有可能作为主元，就是不动的那个。
- 将数按顺序存起来
- 从前往后遍历，将前面的最大的数存起来与当前数比较，如果这个数前面的最大值小于当前值，说明这个数前面都是小于它的数
- 从后往前遍历，将后面的最小的数存起来与当前数比较，如果这个数后面的最小值大于当前值，说明这个数后面都是大于它的数
- 获得两组标记之后，求交集，交集中的数即为
前面的数都小，后面的数都大的主元数了
代码
#include <iostream>
using namespace std;
#include <set>
#include <vector>
const int infn = int(1e9 + 9);
int main() {
ios::sync_with_stdio(0); cin.tie(0);
int t; cin >> t;
vector<int> v;
for(int i = 0; i < t; i++) {int a; cin >> a; v.push_back(a);}
int m = 0;
set<int> sa;
for(int i = 0; i < t; i++) if (m < v[i]) m = v[i], sa.insert(v[i]);
m = infn;
set<int> sb;
for(int i = t - 1; i >= 0; i--) if (m > v[i]) m = v[i], sb.insert(v[i]);
v.clear();
int c = 0;
for (int a : sa) if (sb.find(a) != sb.end()) v.push_back(a), c += 1;
cout << c << endl;
bool f = false;
for (int a : v) {if (f) cout << ' '; cout << a; f = true;}
cout << endl;
return 0;
}