一开始数组开小了,找半天,真的蚌。
这题可以通过枚举例子发现,连续涂的长度一定是除二向上取整,分析也可以发现,涂一个,洪水冲一个,最后也是涂了[n/2]个,所以直接用前缀和处理每一段区间的和,直接枚举[n/2]长度的区间和,来维护涂墙的最大值即可
#include <bits/stdc++.h>
using namespace std;
const int N = 5e6+10;//一定不要忘记开大点
int s[N],i;
int main()
{
int t;scanf("%d",&t);
int rank=0;
while(t--)
{
int n;scanf("%d",&n);
for (i=1;i<=n;i++)
{
char c;cin>>c;
s[i]=s[i-1]+(c-'0');
}
int res=0;
int mid=(n+1)>>1;
for(i=mid;i<=n;i++)
{
res=max(res,s[i]-s[i-mid]);
}
printf("Case #%d: %d\n",++rank,res);
}
return 0;
}