1. 题意看不懂(pass)

2. leetcode480

3. 最长连续1的方案数

题意

给定01字符串s，以及数k, 最多有k次操作,可以将s中的0变成1, 求使得s中连续的1的最多的方案数

eg

1010101  1
输出3

解释
最长的连续1是3, 有3种方案
1110101 1011101 1010111


题解
二分+滑动窗口先求最长的连续1的长度, 然后再滑动窗口这个最长长度判断

#include<bits/stdc++.h>
using namespace std;

string str;
int n, k;

bool Check( int m )
{
    int cnt = 0;
    for( int i = 0; i < m; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
    }
    if( cnt <= k ) return true;
    for( int i = m; i < n; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
        if( str[ i - m ] == '0' ) cnt --;
        if( cnt <= k ) return true;
    }
    return false;
}

int main()
{
    cin >> n >> k;
    cin >> str;
    int Maxlen = 0;
    int l = 0;
    int r = n;
    while( l <= r )
    {
        auto mid = l + r >> 1;
        if( Check(mid) )
        {
            Maxlen = mid;
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    int tot = 0;
    int cnt = 0;
    for( int i = 0; i < Maxlen; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
    }
    if( cnt <= k ) tot ++;
    for( int i = Maxlen; i < n; i ++ )
    {
        if( str[ i ] == '0' ) cnt ++;
        if( str[ i - Maxlen ] == '0' ) cnt --;
        if( cnt <= k ) tot ++;
    }
    cout << tot << endl;
    return 0;
}