洛谷3129bzoj4391
yukuai26
2017-12-23 13:48:44
题目：https://www.luogu.org/problemnew/show/P3129
神奇的贪心，令f[i]表示前i个每次都出比对方稍微大一点的牌，最多能赢几次
g[i]表示从i-n中每次出比对方稍微小一点的牌，最多赢几次。
ans=max(f[i]+g[i+1]) 0<=i<=n
但是方案可能会重合。一般看到这儿就会放弃贪心去想别的算法。但是这是可行的
1：因为限制比原题目宽，所以ans>=真实的答案
2：对于重复取的数a，如果集合中有个没取的数<a,那么在用小的赢的时候可以代替a;
如果>a,那么在用大的赢时可以代替a
用set来记录最接近的数（其实可以用线段树2333）
```cpp
`#include<cstdio>
#include<ctime>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<set>
#define N 200005
using namespace std;
set<int>q1,q2;
int a[N],vis[N],n,ans,f[N],g[N];
inline int read(){
char c=getchar();int tot=1;while ((c<'0'|| c>'9')&&c!='-') c=getchar();if (c=='-'){tot=-1;c=getchar();}
int sum=0;while (c>='0'&&c<='9'){sum=sum*10+c-'0';c=getchar();}return sum*tot;}
int main()
{
scanf("%d",&n);
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]){
q1.insert(i);
q2.insert(-i);
}
}
for(int i=1;i<=n;i++){
set<int>::iterator it=q1.lower_bound(a[i]);
if(it!=q1.end())
q1.erase(it),f[i]=f[i-1]+1;
else f[i]=f[i-1];
}
for(int i=n;i>=1;i--)
{
set<int>::iterator it=q2.lower_bound(-a[i]);
if(it!=q2.end())
q2.erase(it),g[i]=g[i+1]+1;
else g[i]=g[i+1];
}
ans=g[1];
for(int i=1;i<=n;i++){
ans=max(ans,f[i]+g[i+1]);
}
printf("%d",ans);
} `
```