AcWing 562. 壁画
原题链接
中等
作者:
颓废
,
2024-04-05 21:34:17
,
所有人可见
,
阅读 4
思路:一个数组中找一段固定长度的最大的前缀和,(n+1)/2能求出该长度,预处理前缀和后枚举起始位置判断是否最大即可
#include<bits/stdc++.h>
using namespace std;
const int N=5000010;
int n;
char str[N];
int score[N];
int t;
int main(){
cin>>t;
int s=1;
while(t--){
scanf("%d%s",&n,str+1);
memset(score,0,sizeof score);
int res=0;
for(int i=1;i<=n;i++) score[i]=str[i]-'0';
for(int i=1;i<=n;i++){
score[i]+=score[i-1];
}
int k=(n+1)/2;
for(int i=1;i<=n-k+1;i++){
int t=score[i+k-1]-score[i-1];
res=max(res,t);
}
printf("Case #%d: %d\n",s++,res);
}
return 0;
}