黑白奶牛(类似滑动窗口，贪心扫一遍)

黑白奶牛

时间限制: 1 Sec  内存限制: 128 MB

题目描述

有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  0
1  1  0  0  1  1  1  1  0  1  1

样例输出

4

提示

由于K=0，所以不能使用魔法棒，所以挑选编号是5至8的奶牛去参加晚会。

对于50%的数据，1 <= N <= 1000，K = 0，即不能使用魔法棒。
对于100%的数据，1 <= N <= 100000，  1 <= K <=N。

#include<bits/stdc++.h>
using namespace std;
 
int  n, k;
int a[100005];
 
int main(){
    scanf("%d %d", &n, &k);
    a[0] = 1;
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    int l = 1, r = 1;
    int cnt = 0, ans = 0;
    while(r <= n){
        if(a[r++] == 0) cnt++;
        while(cnt > k){
            if(a[l++] == 0) cnt--;
        }
        ans = max(ans, r - l);
    }
    printf("%d\n", ans);
}
/**************************************************************
    Problem: 9743
    User: Xzit02
    Language: C++
    Result: 正确
    Time:12 ms
    Memory:2412 kb
****************************************************************/