B T2 交换
题面
https://ac.nowcoder.com/acm/contest/7612/B
思路
非常裸的一个贪心思想。
观察操作,事实上它将序列首尾相连。故维护一个数组 ,
为以第
位为截止同时为最后一位的连续1的个数,更新
和答案,同时去计算以第
位为开头的连续1的个数
。复杂度
。
特判 的情况,此时序列全为
。
剩下的情况均为有0的情况,更新一次首尾相接的情况 。
代码
#include <iostream> #include <cstdio> #include <cmath> #include <algorithm> #include <cstring> #include <string> #include <queue> #include <stack> #include <vector> #include <set> #include <map> using std::cin;using std::cout;using std::cerr;using std::endl; #define rep(i,a,b) for(int i = a;i <= b;++i) #define per(i,a,b) for(int i = a;i >= b;--i) const int mmax = 1e5; char s[mmax + 10];int b[mmax + 10],n,ans,temp; int main(){ std::ios::sync_with_stdio(0); cin.tie(0); cin>>(s + 1); bool f = 1; n = std::strlen(s + 1); rep(i,1,n){ if(s[i] == '1') { if(f) temp++; b[i] = b[i - 1] + 1; ans = std::max(ans,b[i]); } else f = 0; } if(temp == n){ cout<<temp; return 0; } ans =std::max(ans,b[n] + temp); cout<<ans; return 0; }