原题链接
题目描述：奶牛Bessie和Elsie在玩一种卡牌游戏。一共有2N张卡牌，点数分别为1到2N，每头牛都会分到N张卡牌。 游戏一共分为N轮，因为Bessie太聪明了，她甚至可以预测出每回合Elsie会出什么牌。 每轮游戏里，两头牛分别出一张牌，点数大者获胜。 同时，Bessie有一次机会选择了某个时间点，从那个时候开始，每回合点数少者获胜。 Bessie现在想知道，自己最多能获胜多少轮？
输入格式：第一行：一个整数N。 第2~N+1行：每行一个整数表述Elsie的卡。
输出格式：一个整数表示答案。
输入样例： 4 1 8 4 3
输出样例： 3
解析：一眼看到这倒题好像是一个田忌赛马，但肯定不能直接枚举改规则的时间点。 于是考虑预处理。用pre[i]表示1~i用大牌获胜的规则最多赢的轮数；suf[i]表示从i~n用小牌获胜的轮数。 关于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; }转载于:https://www.cnblogs.com/Gaxc/p/10204275.html
