思路
题意即求一段最大连续子项和,项数为 上取整n/2
先求每个数的前缀和
再求一段子项和,取较大值
输出
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 5e6 + 10;
int T,n;
int sum[N];
char w[N];
int main()
{
cin>>T;
int t = 0;
while(T --)
{
cin>>n;
for(int i = 1; i <= n; i ++)
{
cin>>w[i];
sum[i] = sum[i - 1] + w[i] - '0';
}
int cnt = 0;
int maxv = 0;
if(n % 2) cnt = n / 2 + 1;
else cnt = n / 2;
for(int i = cnt; i <= n; i ++)
maxv = max(maxv, sum[i] - sum[i - cnt]);
t ++; // 因为用while循环 用t来计数
printf("Case #%d: %d\n", t,maxv);
}
return 0;
}