题目
L最近喜欢上了一个卡片游戏，游戏规则是： 2个人一共拿2n张卡片，编号1..2n，每个人n张，然后进行n轮出牌，每轮2个人都打一张牌，，点数大的玩家每次获1分
L可以预测到对方要打牌的顺序。
同时，L有一次机会选择了某个时间点，从那个时候开始，每回合点数少者获胜。
请你帮助L获得最大的分数
输入
第一行是1个整数n
接下来n行表示，对手每次的出牌，根据这些数字，你一定知道了L手上的牌的吧
输出
1个整数，表示L能获得最高分数
样例输入
4
1
8
4
3样例输出
3标签
usaco2015dec
#include<bits/stdc++.h> using namespace std; set<int> l,r; bool flag[100005]; int a[50005],g[50005],f[50005],n; int main(){ scanf("%d",&n); int i; memset(flag,true,sizeof(flag)); for(i=1;i<=n;i++) { scanf("%d",&a[i]); flag[a[i]]=false; } for(i=1;i<=2*n;i++) { if(flag[i]) { r.insert(i); l.insert(-i); } } for( i=1;i<=n;i++) { set<int>::iterator it=r.upper_bound(a[i]); if(it!=r.end()) { r.erase(*it); f[i]=f[i-1]+1; } else f[i]=f[i-1]; } for(i=n;i>=1;i--) { set<int>::iterator it=l.upper_bound(-a[i]); if(it!=l.end()) { l.erase(*it); g[i]=g[i+1]+1; } else g[i]=g[i+1]; } int ans=0; for( i=0;i<=n;i++) { ans=max(ans,f[i]+g[i+1]); } cout<<ans<<endl; }
原文：https://www.cnblogs.com/forever-/p/9736139.html