1 条题解
-
2limingyang LV 10 MOD @ 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