C. Hard Process

题目连接：

http://www.codeforces.com/contest/660/problem/C

Description

You are given an array a with n elements. Each element of a is either 0 or 1.

Let's denote the length of the longest subsegment of consecutive elements in a, consisting of only numbers one, as f(a). You can change no more than k zeroes to ones to maximize f(a).

Input

The first line contains two integers n and k (1 ≤ n ≤ 3·105, 0 ≤ k ≤ n) — the number of elements in a and the parameter k.

The second line contains n integers ai (0 ≤ ai ≤ 1) — the elements of a.

Output

On the first line print a non-negative integer z — the maximal value of f(a) after no more than k changes of zeroes to ones.

On the second line print n integers aj — the elements of the array a after the changes.

If there are multiple answers, you can print any one of them.

Sample Input

7 1

1 0 0 1 1 0 1

Sample Output

4

1 0 0 1 1 1 1

Hint

题意

你有n个非0就是1的数字，你可以修改最多k个，使得0变成1

然后问你修改之后，最长的连续1的串是多长？

题解：

维护一个前缀0的个数

然后对于每个位置，直接暴力二分就好了，二分这个位置最远能够延展到哪儿

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6;

int n,k;

int a[maxn],sum[maxn];

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=1;i<=n;i++)

    {

        scanf("%d",&a[i]);

        a[i]=1-a[i];

    }

    for(int i=1;i<=n;i++)

        sum[i]=sum[i-1]+a[i];

    int ans1=0,ans2=0;

    for(int i=1;i<=n;i++)

    {

        int l = i,r = n,ans=0;

        while(l<=r)

        {

            int mid=(l+r)/2;

            if(sum[mid]-sum[i-1]>k)r=mid-1;

            else l=mid+1,ans=mid-i+1;

        }

        if(ans>ans1)

        {

            ans1=ans;

            ans2=i;

        }

    }

    cout<<ans1<<endl;

    for(int i=ans2;i<=n;i++)

    {

        if(ans1==0)break;

        if(a[i]==1)a[i]=0;

        if(a[i]==0)ans1--;

    }

    for(int i=1;i<=n;i++)

        cout<<1-a[i]<<" ";

}

巴特西

Educational Codeforces Round 11 C. Hard Process 二分