题意翻译

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

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

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

输入格式

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

第二行包含个整数。每个整数只存在或两种情况。

输出格式

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

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

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

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

数据范围和约定

对于的数据， 。

分析

一道贪心好题。

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

考虑如何优化这个算法。

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

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

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

若向后拓展位后的总数不大于，即不大于，则拓展是可行的。直接拓展即可。

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

时间复杂度为，足以通过本题。

剩下的详见代码注释

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

THE END