题解

1 条题解

  • 2
    @ 2020-07-04 20:46:58

    \(\large\texttt{十年OI一场空,少个“-1”见祖宗!}\)
    这道题听\(b6e0\)\(\huge\texttt{大佬}\)说,有一种\(O(n)\)的神奇方法,可本蒟蒻不会……
    于是,我是用了较为暴力的\(O(n*log(n))\)方法。
    这种方法具体就是:先以每个\(0\)开头,以下一个\(0\)的前一位结尾,分成多组。然后在每一位做二分查找,按组数查找合适的结尾,在经过计算算出总长度,最后输出最长长度。
    于是乎,代码就变成了这样:

    #include <bits/stdc++.h>
    using namespace std;
    #define l s.size()
    int main(){
        string s;
        int n, maxx=0;
        cin >> s >> n;
        int a[l];
        if (s[0]=='0') a[0]=1; 
        else a[0]=0;
        for (int i=1; i<l; i++){
                if (s[i]=='0') a[i]=a[i-1]+1;
                else a[i]=a[i-1];
            }//先算出每一位所对应的组数 
        for (int i=0; i<l; i++){
            int x;
            if (s[i]=='0') x=a[i]+n-1;
            if (s[i]=='1') x=a[i]+n;//然后计算最长能延伸到第几组 
            int f;
            if (a[l-1]<x) f=l-i;
            else f=upper_bound(a+i, a+l, x)-a-i;//进行二分查找 
            maxx=max(maxx, f);//打擂台比最大值 
        }
        cout << maxx << endl;
        return 0;
    }
    
  • 1

信息

ID
1019
难度
4
分类
字符串 | 二分查找 点击显示
标签
递交数
10
已通过
2
通过率
20%
上传者