网站名 注册,建设商场黄金网站,仿制网站侵权行为,合肥建设管理学校网站首页1.披萨和西蓝花 - 蓝桥云课
1. 披萨和西蓝花
问题描述 在接下来的 N 天里#xff08;编号从 1 到 N#xff09;#xff0c;坤坤计划烹饪披萨或西兰花。他写下一个长度为 N 的字符串 A#xff0c;对于每个有效的 i#xff0c;如果字符 Ai 是 1#xff0c;那么他将在第 i…1.披萨和西蓝花 - 蓝桥云课
1. 披萨和西蓝花
问题描述 在接下来的 N 天里编号从 1 到 N坤坤计划烹饪披萨或西兰花。他写下一个长度为 N 的字符串 A对于每个有效的 i如果字符 Ai 是 1那么他将在第 i 天做西兰花。 坤坤的儿子小沸就像大多数孩子一样喜欢披萨但讨厌西兰花。他想选择一个 A 的长度为 K 的子串并将这个子串中的每个字符 0 改为 1。然后让我们定义披萨时间为坤坤连续做披萨的最大天数。请找出小沸可以达到的最大披萨时间。
输入格式 第一行包含两个用空格分隔的整数 N 和 K1 ≤ K ≤ N ≤ 10^5。 第二行包含一个长度为 N 的只包含 0 和 1 的字符串 A。
输出格式 打印一行其中包含一个整数——最大的披萨时间。
样例输入
13 2
0101110000101
样例输出
5思路如下
先暴力枚举0~n-1作为k的起点比如以i为下标作为起点我将这个连续1部分分成三个部分因为下标为0开始所以找出i-1往左的连续1和ik往右的连续1再加上中间的k即可。但是当i为n-k的时候此时还是能取到n-k~n作为1当in-k,k能变成1的范围就取不到k了 则min(k,n-k)即可因为当i到达最后一个下标最大可以变一个1.
代码如下
#include iostream
#include vector
#includequeue
#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 xk;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的数量
代码如下
#includeiostream
#includestring
#includealgorithm
using namespace std;
const int N 1e410;
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[i1] 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[i1];suffix[i] a[i];}}int ans -1e9;for(int i 1 ; i n-k1 ; i){int sum 0;sum k pre[i-1] suffix[ik];ans max(ans,sum);}cout ans;return 0;
}
