2점--CodeForces-660C(2점짜리 응용도 자로 뽑을 수 있음)
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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Google Gson 변환 Json 문자열 및 개체(날짜, 열거된 변환)예는 틀림없이 성공적으로 실행될 것이다. 대상을 고려하여 몇 가지 종류를 더 썼다. 1. 날짜의 변환은 Create GsonBuilder에 등록된 날짜의 형식이 필요합니다. 2. 열거 클래스에 대해 기본 변환이라면 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.