AcWing 562. 壁画(Java 前缀和)
原题链接
中等
作者:
DPF
,
2024-04-10 10:35:39
,
所有人可见
,
阅读 2
//有题目知道墙只能从两头坏,而最终作画区间是连续的
//所以依次比较出reserve长度的连续墙面美观值的最大值作为每个输出结果
//reserve = 墙数/2+1;(向上取整)
import java.util.*;
import java.io.*;
public class Main{
public static int[] arr = new int[(int)5e6+10];
public static int[] preSum = new int[(int)5e6+10];
public static void main(String[] args){
Scanner sc = new Scanner(new BufferedInputStream(System.in));
int n = sc.nextInt();
for(int k = 0;k<n;k++){
int t = sc.nextInt();
String nums = sc.next();
for(int i = 1;i<=t;i++){
arr[i] = Character.digit(nums.charAt(i-1), 10);
}
arr[t+1] = 0;
for(int i = 1;i<=t;i++){
preSum[i] = preSum[i-1]+arr[i];
}
int reseve = t-t/2;
int l = 1;
int r = l+reseve-1;
int max = 0;
while(r<=t){
max = Math.max(max, preSum[r]-preSum[l-1]);
r++;
l++;
}
System.out.printf("Case #%d: %d\n",k+1,max);
}
}
}