第二篇博客,高兴高兴真高兴!!!
#206.黑白奶牛
有N只奶牛从左往右排成一行,编号是1至N。这N只奶牛当中,有一些奶牛是黑色的,其余的是白色的。
color[i]表示第i只奶牛的颜色,如果color[i]=0则表示第i头奶牛是黑色的,如果color[i]=1则表示第i头奶牛是白色的。
六一奶牛儿童节快到了,农场主Farmer John要从这N头奶牛当中,挑选尽可能多的奶牛去参加晚会。
Farmer John挑选奶牛的原则是:挑选编号是连续的一段奶牛,这一段奶牛的颜色必须全部是白色的。
Farmer John有一个魔法棒,每用一次魔法棒就可以把一头黑色的奶牛变成一头白色的奶牛,魔法棒最多只能使用K次。
在上述条件下,最多可以有多少头奶牛去参加晚会呢?
输入输出格式
输入格式:
第一行,两个整数,N和K。
第二行,N个整数,第i个整数就是color[i],color[i]要么是0,要么是1。
输出格式:
一个整数,表示最多有多少头奶牛可以去参加晚会。
输入输出样例
输入样例一:
11 01 1 0 0 1 1 1 1 0 1 1
输出样例一:
4
输入样例二:
11 11 1 0 0 1 1 1 1 0 1 1
输出样例二:
7
说明
样例说明:
样例一说明:由于K=0,所以不能使用魔法棒,所以挑选编号是5至8的奶牛去参加晚会。
样例二说明:由于K=1,所以最多可以使用1次魔法棒,使用魔法棒把第9头奶牛变成白色奶牛,然后挑选编号是5至11的奶牛去参加晚会。
//WZL//黑白奶牛//数组滚动(尺取法)#include#include #include using namespace std;int n,l,k,hehe1[100000],a[100000],sum,smax;int main(){ cin>>n>>k;//输入数量和魔法棒 for(int i=1;i<=n;i++) { cin>>hehe1[i];//保存奶牛 a[i]=a[i-1];//前缀和 if(hehe1[i]==0) a[i]++;//前缀黑牛 } for(int i=1;i<=n;i++) { if(a[i]-a[l]<=k)//如果这一段黑牛小于魔法棒数 { sum++; if(i==n&&sum>smax)//如果为最末尾牛(i==n)而且这个方案>目前最大值 { smax=sum;//记录最大值 } } else//否则 { if(sum>smax)//找最大值 { smax=sum; } l++;//换一段黑牛再找 } } cout<