[CodeChef]SCHEDULE 解题报告

解题报告

解题说明

一开始写了个普通二分，连续天数一超过 $lim$ 就把这天取反，结果全 WA ……
后来发现这样不能取到最优方案，因为若是对一段区间的最右边的数取反，可能会影响右边的区间。
看了题解后发现不用依次枚举字符串中的每一位，只要预处理出每个连续区间的长度 $len$，$len/(lim+1)$ 就是这个区间需要取反的数的个数，$lim$ 等于一的时候特判一下就行了。

代码

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000000+7;
int T,n,k,len[N],cnt;
char s[N];
int spj(int k){
    int num=0;
    for(int i=1;i<=n;i++)
        if(i%2==k){ if(s[i]=='0') num+=1; }
        else { if(s[i]=='1') num+=1; }
    return num;
}
bool judge(int lim){
    if(lim!=1){
        int num=0;
        for(int i=1;i<=cnt;i++)
            if(len[i]>lim) num+=len[i]/(lim+1);
        return num<=k;
    }
    else{
        int num=min(spj(1),spj(0));
        return num<=k;
    }
}
int main(){
    //freopen("1.txt","r",stdin);
    cin>>T;
    while(T--){
        int lst=0,l=1,r=0,mid;cnt=0;
        scanf("%d%d%s",&n,&k,s+1);
        for(int i=1;i<=n;i++)
            if(s[i]!=s[i+1]){ len[++cnt]=i-lst;lst=i;r=max(r,len[cnt]); }
        while(l<r){
            mid=(l+r)>>1;
            if(judge(mid)) r=mid;
            else l=mid+1;
        }
        printf("%d\n",r);
    }
    return 0;
}