P3718 [AHOI2017初中组]alter

贪心+二分答案

二分最终答案长度

主要问题在check上

~~我代码写得巨丑，大家还是不要看我的代码了~~

------------

1:当mid大于1的时候，贪心策略是这样的：

当前连续的长度大于mid时，我不反转最后一个，我也不管它具体反转哪一个，我直接跳过这mid+1个，也就是开始处理i+1。举个例子，
mid=3,k=1,NNNNNNN,我反转第4个，变成NNNFNNN
mid=3,k=1,NNNNFFF,我反转前3个的任意一个
不管怎么反转，前4个对后面是没有影响了，那我就不用管具体怎么反转的

2:当mid等于1的时候，贪心策略是这样的：

跑两遍check,反转第一个，或者不反转第一个，两种情况有一个能行就ok

------------

#include <iostream>

#include <cstdio>

#include <queue>

#include <algorithm>

#include <cmath>

#include <cstring>

#define inf 2147483647

#define N 1000010

#define p(a) putchar(a)

#define For(i,a,b) for(int i=a;i<=b;++i)

//by war

//2019.8.13

using namespace std;

int n,k,l,r,mid,a[N],cnt,now;

char c[N];

void in(int &x){

    int y=;char c=getchar();x=;

    while(c<''||c>''){if(c=='-')y=-;c=getchar();}

    while(c<=''&&c>=''){ x=(x<<)+(x<<)+c-'';c=getchar();}

    x*=y;

}

void o(int x){

    if(x<){p('-');x=-x;}

    if(x>)o(x/);

    p(x%+'');

}

bool check1(int x,int t){

    int lf=k-;

    For(i,,n)

        if(c[i]=='N')

            a[i]=;

        else

            a[i]=;

    cnt=;now=t;

    For(i,,n){

        if(a[i]==now){

            ++cnt;

            if(cnt>x){

                a[i]^=;

                if(x!=){

                    now=a[i+];

                    cnt=;

                }

                else{

                    now=a[i];

                    cnt=;

                }

                if(--lf<)

                    return ;

            }

        }

        else{

            now=a[i];

            cnt=;

        }

    }

    return ;

}

bool check(int x){

    int lf=k;

    For(i,,n)

        if(c[i]=='N')

            a[i]=;

        else

            a[i]=;

    cnt=;now=a[];

    For(i,,n){

        if(a[i]==now){

            ++cnt;

            if(cnt>x){

                a[i]^=;

                if(x!=){

                    now=a[i+];

                    cnt=;

                }

                else{

                    now=a[i];

                    cnt=;

                }

                if(--lf<){

                    if(x==){

                        if(check1(x,a[]^))

                            return ;

                        return ;

                    }

                    return ;

                }

            }

        }

        else{

            now=a[i];

            cnt=;

        }

    }

    return ;

}

signed main(){

    in(n);in(k);

    cin>>(c+);

    l=;r=n;

    while(l<r){

        mid=(l+r)>>;

        if(check(mid))

            r=mid;

        else

            l=mid+;

    }

    o(l);

    return ;

}

巴特西

P3718 [AHOI2017初中组]alter

最新文章

热门文章