本文主要是介绍壁画 Google Kickstart2018 Round H Problem B（前缀和+模拟），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：
Thanh 想在一面被均分为 N段的墙上画一幅精美的壁画。
每段墙面都有一个美观评分，这表示它的美观程度（如果它的上面有画的话）。
不幸的是，由于洪水泛滥，墙体开始崩溃，所以他需要加快他的作画进度！
每天 Thanh 可以绘制一段墙体。
在第一天，他可以自由的选择任意一段墙面进行绘制。
在接下来的每一天，他只能选择与绘制完成的墙面相邻的墙段进行作画，因为他不想分开壁画。
在每天结束时，一段未被涂颜料的墙将被摧毁（Thanh 使用的是防水涂料，因此涂漆的部分不能被破坏），且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻。
Thanh 的壁画的总体美观程度将等于他作画的所有墙段的美观评分的总和。
Thanh想要保证，无论墙壁是如何被摧毁的，他都可以达到至少 B 的美观总分。
请问他能够保证达到的美观总分 B 的最大值是多少。
输入格式：
第一行包含整数 T，表示共有 T组测试数据。
每组数据的第一行包含整数 N。
第二行包含一个长度为 N 的字符串，字符串由数字 0∼9 构成，第 i 个字符表示第 i 段墙面被上色后能达到的美观评分。
输出格式：
每组数据输出一个结果，每个结果占一行。
结果表示为
Case #x: y，其中 x 为组别编号（从 11 开始），y 为 Thanh 可以保证达到的美观评分的最大值。
数据范围：
1≤T≤100,
存在一个测试点N=5∗106,其他测试点均满足2≤N≤100
输入样例：
4
4
1332
4
9583
3
616
10
1029384756
输出样例：
Case #1: 6
Case #2: 14
Case #3: 7
Case #4: 31
样例解释：
在第一个样例中，无论墙壁如何被破坏，Thanh都可以获得 66 分的美观总分。在第一天，他可以随便选一个美观评分3的墙段进行绘画。在一天结束时，第一部分或第四部分将被摧毁，但无论哪一部分都无关紧要。在第二天，他都可以在另一段美观评分 33 的墙段上作画。
在第二个样例中，Thanh 在第一天选择最左边的美观评分为 99 的墙段上作画。在第一天结束时唯一可以被毁掉的墙体是最右边的那段墙体，因为最左边的墙壁被涂上了颜料。在第二天，他可以选择在左数第二段评分为 55 的墙面上作画。然后右数第二段墙体被摧毁。请注意，在第二天，Thanh不能选择绘制第三段墙面，因为它不与任何其他作画墙面相邻。这样可以获得 1414 分的美观总分。
思路：
根据题目我们可以知道，被水破坏的画一定是在左右两边，可以模拟找到规律是看成是对称的。
因为（且被毁掉的墙段一定只与一段还未被毁掉的墙面相邻）
根据样例，我们可以看出来当字符串长度为奇数的时候，被画的墙是比被破坏的墙多一次的
所以我们要向上取整给出公式：（x+y+1）/ y --->x中有多少个y
换成题意就是n中有多少个2 -------> （n+1）/ 2
AC代码：
#include<iostream>
#include<cmath>
#include<cstring>using namespace std;const int N = 5e6+10;
int s[N];
char str[N];int main()
{int t,x=1;scanf("%d ",&t);while(t--){int n;scanf("%d ", &n);//str+1的意思就是让字符串从1开始读scanf("%s",str + 1);//求出前缀和for(int i=1;i<=n;i++){s[i] = s[i-1] + str[i] - '0';}int res = 0,k = (n+1)>>1;//可以把k看成一个滑块，不断滑动一位去找出最大值for(int i=k;i<=n;i++){res = max(res, s[i] - s[i-k]);}printf("Case #%d: %d\n",x,res);x++;}return 0;
}这篇关于壁画 Google Kickstart2018 Round H Problem B（前缀和+模拟）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
