题目描述：奶牛Bessie和Elsie在玩一种卡牌游戏。一共有2N张卡牌，点数分别为1到2N，每头牛都会分到N张卡牌。
游戏一共分为N轮，因为Bessie太聪明了，她甚至可以预测出每回合Elsie会出什么牌。
每轮游戏里，两头牛分别出一张牌，点数大者获胜。
同时，Bessie有一次机会选择了某个时间点，从那个时候开始，每回合点数少者获胜。
Bessie现在想知道，自己最多能获胜多少轮？
输入格式：第一行：一个整数N。
第2~N+1行：每行一个整数表述Elsie的卡。
输出格式：一个整数表示答案。
输入样例：
4
1
8
4
3
输出样例：
3
解析：一眼看到这倒题好像是一个田忌赛马，但肯定不能直接枚举改规则的时间点。
于是考虑预处理。用pre[i]表示1i用大牌获胜的规则最多赢的轮数；suf[i]表示从in用小牌获胜的轮数。
关于pre和suf的预处理，可以用set来实现，每次从set中lower_bound进行寻找，之后删除即可。
最后的答案便是max{pre[i]+suf[i+1]}。
关于这个贪心的正确性，证明也比较简单。
因为pre和suf中删去的数总个数为n，若有一个元素重复，那么必定有一个元素不被两个删去。
设哪个元素为x，都被删去的数为y，那么分两种情况讨论。
若x>y，那么x可以在大的获胜的规则中替换y。
若x<y，那么x可以在小的获胜的规则中替换x。
所以对答案不会造成影响。
代码如下：
#include<cstdio>
#include<set>
using namespace std;
const int maxn = 5e4 + 5;
int n, vis[maxn << 1], pre[maxn], suf[maxn], a[maxn], ans;
set <int> se1, se2;
int read(void) {
char c; while (c = getchar(), c < '0' || c > '9'); int x = c - '0';
while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x;
}
int main() {
n = read();
for (int i = 1; i <= n; ++ i) {
a[i] = read(); vis[a[i]] = 1;
}
for (int i = 1; i <= n * 2; ++ i)
if (!vis[i]) se1.insert(i), se2.insert(-i);
for (int i = 1; i <= n; ++ i) {
set <int>::iterator it = se1.lower_bound(a[i]);
if (it != se1.end()) pre[i] = pre[i - 1] + 1, se1.erase(it);
else pre[i] = pre[i - 1];
}
for (int i = n; i ; -- i) {
set <int>::iterator it = se2.lower_bound(-a[i]);
if (it != se2.end()) suf[i] = suf[i + 1] + 1, se2.erase(it);
else suf[i] = suf[i + 1];
}
for (int i = 0; i <= n; ++ i) ans = max(ans, pre[i] + suf[i + 1]);
printf("%d", ans);
return 0;
}