AcWing 562. 壁画
原题链接
中等
作者:
ofs
,
2024-04-11 23:49:00
,
所有人可见
,
阅读 2
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5000010;
int n;
int s[N];
char str[N];
//注意每次都从两边开始坏,不会从中间坏
//注意墙的长度是n/2的上取整
int main()
{
int T;
scanf("%d", &T);
//注意证明过程没有需要写入代码的,证明过程自己证明出来就好
for (int cases = 1; cases <= T; cases ++ )//T组测试数据,每组测试数据都是单独的n段墙
{
scanf("%d", &n);
scanf("%s", str + 1);//下标从1开始储存
for (int i = 1; i <= n; i ++ )//循环的时候下标从1开始,算前缀和
s[i] = s[i - 1] + str[i] - '0';//减去’0‘,目的是把字符数字转成对应的int
int res = 0, m = (n + 1) / 2;//墙的长度(上取整)
for (int i = m; i <= n; i ++ )
res = max(res, s[i] - s[i - m]);//s[i] - s[i - m]代表长为n/2上取整的墙的美观程度
printf("Case #%d: %d\n", cases, res);
}
return 0;
}