AcWing 562. 壁画-前缀合
原题链接
中等
作者:
CqAq
,
2024-04-10 17:10:29
,
所有人可见
,
阅读 3
算法1
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N = 5E6 + 9;
int t;
void orz(int num, string s){
int tm[N] = {0};
int len = s.size();
s = "!" + s;
for(int i = 1; i <= len; ++ i) tm[i] = s[i] - '0';
for(int i = 1; i <= len; ++ i) tm[i] += tm[i - 1];
int k = len / 2 + (len % 2 ? 1 : 0);
int mmax = 0;
for(int i = 0; i + k <= len; i ++){
mmax = max(mmax, tm[i + k] - tm[i]);
}
cout << "Case #" << num << ": " << mmax << '\n';
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin >> t;
int tag = 1;
while(t --){
int k; cin >> k;
string s; cin >> s;
orz(tag, s);
tag ++;
}
return 0;
}