#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int main() {
// 取主元 左小右大 判断主元个数
int n, a[100000], b[2][100000], max = 0, min = INF;
set<int> result;
cin >> n;
for (int i = 0; i < n; i++){
cin >> a[i];
}
// 顺序遍历一边 记录左边每个下标位置的最大元素
for (int i = 0; i < n; i++){
if(a[i] > max){
max = a[i];
}
b[0][i] = max;
}
// 逆序遍历 比较右边最小元素并记录
for (int i = n-1 ; i >= 0; i--){
if(a[i] < min){
min = a[i];
}
b[1][i] = min;
// 比较当前元素 左右最值
// 大于等于左边最大值 小于等于右边最小值 加入主元
if(b[0][i] <= a[i] && a[i] <= b[1][i]){
result.insert(a[i]);
}
}
if(result.size())
cout << result.size() << endl;
// 测试点二 没有元素需要输出多一个空行
else
cout << result.size() << endl << endl;
int flag = 0;
for(auto r : result)
cout << ( flag++ ? " " : "") << r;
}
当时想的时候感觉跟前不久写的 “有几个PAT” 那题比较相似，所以就试了下用当时那个循环标记并记录的方法。然后蒙对了。除了有一个意料之外的格式错误。
测试点二 Presentation Error，当时还以为是我思路有问题，结果有误。结果参考别人的一看，这个是格式问题。因为平时都是结果错太多了，看到红色的下意识都以为是结果错了，没想到原来只是格式错误。
以后有必要积累下OJ系统的评测反馈英语的意思是什么。
还有，结合本题卡测试点，跟前一题 “火星数字” 做一个比较，发现大多数题目卡测试点主要在于某些边界上。最常见是 0 的时候，这一个题和前一题都出现了。或者是最大元素时候的情况，“火星数字”那就有一个低位最高时候进位的问题。
或者是某些样例中偷偷给出的特殊条件，还是“火星数字”，因为13进制，13的倍数都是高位，都要特殊处理。
所以以后卡测试点的时候可以往这些边界, 或者特殊情况考虑。
看别人还有一种方法将排好序的序列与原序列比较，且当前元素大于左边元素的最大值。
因为如果不满足大于左边的条件（判断右边应该也可以），比如
5 4 3 2 1（排序前）
|
1 2 3 4 5（排序后）
可以看到，有可能是序列存在左边大于右边的情况，在排序后刚好左右调换了位置。这确实能够满足元素排序后位置不变，但是不能满足题目的条件，“主元小的元素放到它的左边，比主元大的元素放到它的右边”。
算法笔记里面提到了，该题和几个PAT的题目都可以用到一个递推的方法，即通过预处理标记元素左右的数据，再处理。