题意翻译

给你一个数组，其中有$n$个元素，每个元素不是$0$就是$1$。

现在可以进行$k$次操作，每次操作可以改变数组中的一个元素（只能改成$0$或$1$）。

请求出操作后最长连续$1$的序列的长度，并输出操作后的序列。

输入格式

第一行输入两个整数$n$和$k$，分别代表元素的个数与可以进行的操作数。

第二行包含$n$个整数$a_1 , a_2 …… a_n$。每个整数只存在$1$或$0$两种情况。

输出格式

第一行为一个整数$z$，表示最长连续$1$的序列长度。

第二行包含$n$个整数，表示操作后的序列。

如果有多个答案，请输出其中的任意一种答案。

Input & Output ‘s examples

Input ‘s eg 1

7 1
1 0 0 1 1 0 1

Output ‘s eg 1

4
1 0 0 1 1 1 1

Input ‘s eg 2

10 2
1 0 0 1 0 1 0 1 0 1

Output ‘s eg 2

5
1 0 0 1 1 1 1 1 0 1

数据范围和约定

对于$100\%$的数据， $1 < n < 3 * 10^5 , 0 < k < n$。

分析

一道贪心好题。

先来看朴素做法：暴力枚举区间，然后暴力统计其中$0$的数量，时间复杂度为$O(n^3)$，显然无法通过

考虑如何优化这个算法。

显然，对于一段含有$0$的区间，我们让区间中所有$0$填满是最优的。

因此我们只需要维护一段区间，让这段区间中$0$的个数小于等于$k$即可。

这样的话，我们可以直接从第$1$位开始拓展一段区间。初始时，这段区间的$l , r$均为$1$，即$[1 , 1]$。

若向后拓展$1$位后$0$的总数不大于$k$，即$[l , r + 1]$不大于$k$，则拓展是可行的。直接拓展即可。

否则将$l$右移，直到这段区间中$0$的数量小于$k$为止。

时间复杂度为$O(n)$，足以通过本题。

剩下的详见代码注释

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 300001

using namespace std;

int n , k;
int a[N];
ll ans = 0 , cnt = 0;   //cnt为0的个数
int L , R;     //最终答案的那段连续为1的区间的左右端点


int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    for(int l = 1 , r = 1; r <= n; r ++){
        cnt += (a[r] == 0 ? 1 : 0);     
        if(cnt > k){    //如果0的数量大于k，则左端点右移
            cnt -= (a[l] == 0 ? 1 : 0);
            l ++;
        }
        if(r - l + 1 > ans){     //如果当前连续1的序列长度大于当前的答案，则更新
            ans = r - l + 1;
            L = l;
            R = r;
        }
    }
    cout << ans << "\n";        //最后输出即可
    for(int i = 1; i <= n; i ++){
        if(L <= i && i <= R){
            cout << "1" << " ";
        }
        else{
            cout << a[i] << " ";
        }
    }
    return 0;
}