[NC204370] 牛牛的木板

题目描述

牛牛从牛毕那里拿了一根长度为n的白木板，木板被等分成了 $n$ 段（没有被切割，只是虚拟划分成了 $n$ 段），其中有些段被牛毕用颜料染成了黑色。

牛牛非常不喜欢黑色，它找来了一桶清洗剂决定对木板进行清洗，但是牛牛发现自己的清洗剂最多只能清洗 $m$ 段。
清洗完后，牛牛会把木板锯成纯色的几段。例如假设木板是 （黑黑黑白白白白黑黑黑 ），就会被锯成（黑黑黑）（白白白白）（黑黑黑）三段。
牛牛想知道，它足够聪明地清洗木板，能获得的纯白色木板的最大长度是多少。

#示例1

输入

1
6,1, [1,0,0,1,1,1]

返回值

1
4

说明

1
染成了[1,0,1,1,1,1]

#示例2

输入

1
6,2, [1,0,0,1,1,1]

返回值

1
6

说明

1
染成了[1,1,1,1,1,1]

备注:

给定 $n,m$ 两个整数
和一个长度为 $n$ 的数组 $a$ , 为 $1$ 表示白色，为 $0$ 表示黑色
$(1≤n≤10^6 , 1≤m≤n)$
$(0≤a_i≤1)$

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int 
 * @param m int 
 * @param a intvector 
 * @return int
 */
int solve(int n, int m, vector<int>& a) {
    int l=0,r=0,ans=0;
    while(r<n){
        if(a[r]){
            r++;
        }else{
            r++;
            m--;
            if(m<0){
                while(a[l]) l++;
                l++;
                m++;
            }
        }
        ans = max(ans,r-l);
    }
    return ans;
}

题解

使用双指针优先右侧移动,如果用完m就将左侧右移,不断用max求最大值

  • 第一次用的尺举法 $TLE$ 了, 难受, 这次参考了别人的写法学会了如何正确使用尺举法.
  • 多刷题、多刷题……