题意翻译

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

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

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

输入格式

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

第二行包含 $n$ 个整数 $a_{1}, a_{2} \dots \dots a_{n}$ 。每个整数只存在 $1$ 或 $0$ 两种情况。

输出格式

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

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

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

Input & Output ‘s examples

Input ‘s eg 1

markdown

7 1
1 0 0 1 1 0 1

Output ‘s eg 1

markdown

4
1 0 0 1 1 1 1

Input ‘s eg 2

markdown

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

Output ‘s eg 2

markdown

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]

cpp

#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;
}