AtCoder Regular Contest 088 D Wide Flip

题目链接https://arc088.contest.atcoder.jp/tasks/arc088_b

题意:我们可以对字符串里任意长度大于等于k的区间里的字符进行翻转,即1变成00变成1,求这个k的最大值。

思路:考虑相邻两个不同的字符s[x],s[x+1],我们要改变一个字符使得两个字符相同,则可以操作max(len-x,x)长度的区间达成这样的目的,也即把一端长度较长的全部翻转,这样到最后就可以把整个字符串变成用同一字符的字符串,如果全是1,再把整个字符串翻转一下即可,所以答案就是min(k,max(len-x,x))

int main(){
    string s;
    cin>>s;
    int ans=INF,len=s.length();
    for (int i=0;i<len-1;i++){
        if (s[i]!=s[i+1]) ans=min(ans,max(len-i-1,i+1));
    }
    if (ans==INF) cout<<len<<endl;
    else cout<<ans<<endl;
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注