洛谷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）

`#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);  
}  `