【16届蓝桥杯寒假刷题营】第1期DAY4

1.披萨和西蓝花 - 蓝桥云课

1. 披萨和西蓝花

问题描述
在接下来的 N 天里（编号从 1 到 N），坤坤计划烹饪披萨或西兰花。他写下一个长度为 N 的字符串 A，对于每个有效的 i，如果字符 Ai 是 '1'，那么他将在第 i 天做西兰花。
坤坤的儿子小沸，就像大多数孩子一样，喜欢披萨但讨厌西兰花。他想选择一个 A 的长度为 K 的子串，并将这个子串中的每个字符 '0' 改为 '1'。然后，让我们定义披萨时间为坤坤连续做披萨的最大天数。请找出小沸可以达到的最大披萨时间。

输入格式
第一行包含两个用空格分隔的整数 N 和 K（1 ≤ K ≤ N ≤ 10^5）。
第二行包含一个长度为 N 的只包含 0 和 1 的字符串 A。

输出格式
打印一行，其中包含一个整数——最大的披萨时间。

样例输入

13 2
0101110000101

样例输出

5

思路如下：

先暴力，枚举0~n-1作为k的起点，比如：以i为下标作为起点，我将这个连续1部分，分成三个部分，因为下标为0开始，所以找出i-1往左的连续1和i+k往右的连续1，再加上中间的k即可。但是，当i为n-k的时候，此时还是能取到n-k~n作为1，当i>n-k,k能变成1的范围就取不到k了，                 则min(k,n-k)即可，因为当i到达最后一个下标，最大可以变一个1.

代码如下：

#include <iostream>
#include <vector>
#include<queue>
#include <algorithm>
#include <cstring>
using namespace std;
int ans = -1e9;
string s;
int n,k;
int f(int x)
{	int sum = 0;
//	sum = min(k,n-x);if(x + k )int a1 = x-1;int a2 = x+k;while(a1 >= 0 && s[a1] == '1'){sum++;a1--;}while(a2 < n && s[a2] == '1'){sum++;a2++;}return sum;
}
int main() 
{cin >> n >> k >> s;for(int i = 0 ; i < n ; i++){ans = max(f(i),ans);}cout << ans;return 0;
}

思路2：

前缀和+后缀和，记录连续1的数量

代码如下：

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
const int N = 1e4+10;
int n,k;
int pre[N];
int suffix[N];
string s;
int a[N];
int main()
{cin >> n >> k >> s;for(int i = 0 ; i < n ; i++){a[i+1] = s[i]-'0';}for(int i = 1 ; i <= n ; i++){if(a[i]){pre[i] = pre[i-1];pre[i] += a[i];}}for(int i = n ; i >= 1 ; i--){if(a[i]){suffix[i] = suffix[i+1];suffix[i] += a[i];}}int ans = -1e9;for(int i = 1 ; i <= n-k+1 ; i++){int sum = 0;sum = k + pre[i-1] + suffix[i+k];ans = max(ans,sum);}cout << ans;return 0;
}