首页 技术 正文
技术 2022年11月24日
0 收藏 806 点赞 3,509 浏览 1336 个字

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

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/142101.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:875 阅读:5,090
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:3,509
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:565 阅读:4,320
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:730 阅读:4,315
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:4,920
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,105
发表评论
暂无评论

还没有评论呢,快来抢沙发~

助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站