2점--CodeForces-660C(2점짜리 응용도 자로 뽑을 수 있음)

A - Hard Process
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 kchanges 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.
Example
Input
7 1
1 0 0 1 1 0 1

Output
4
1 0 0 1 1 1 1

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

Output
5
1 0 0 1 1 1 1 1 0 1

          
이 문제의 뜻은 0.1로 구성된 그룹을 정하면 k개 0을 1로 바꾸고 최종적으로 얻을 수 있는 연속적인 1의 최대 길이를 묻는 것이다.하나의 그룹으로 현재 위치가 모두 몇 개인지 기록하고 폭력적으로 가장 긴 줄의 마지막 줄을 열거하며 2분으로 가장 긴 줄의 첫 번째 1의 위치를 찾습니다.결과를 업데이트하고 가장 긴 줄의 시작과 끝 위치를 기록하고 마지막에 출력하면 됩니다.
//  main.cpp
//  temp
//
//  Created by Sly on 2017/2/27.
//  Copyright © 2017  Sly. All rights reserved.
//

#include    //  
#include 
#include 
#include 
#define N 100000*3
int t[N];
int a[N];
int n,k;
int Bin(int x)   //  
{
    int mid;
    int l=1;
    int r=x;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(t[x]-t[mid-1]<=k)
            r=mid-1;
        else l=mid+1;
    }
    return l;
}
int main()
{
    int i;
    while(scanf("%d %d",&n,&k)!=EOF)
    {
        t[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            if(!a[i])t[i]=t[i-1]+1;
            else t[i]=t[i-1];
        }
        int ans=0;
        int l=0,r=0;
        for(i=1;i<=n;i++)
        {
            int f=Bin(i);
            if(i-f+1>ans)
            {
                ans=i-f+1;
                l=f;
                r=i;
            }
        }
        printf("%d
",ans); for(i=1;i<=n;i++) { if(i>=l&&i<=r) { printf("1"); if(i!=n)printf(" "); else printf("
"); } else { printf("%d",a[i]); if(i!=n)printf(" "); else printf("
"); } } } return 0; }

좋은 웹페이지 즐겨찾기