two_pointers

CF660C

/*
reference:
	
translation:
	n个长度的01串，可以改变k个0到1，求最长连续1的长度
	n<=3e5+10,1<=k<=n<=3e5+10
	->即是求最长只包含k个0的01串长度 
solution:
	1.O(n^3)枚举左右端点，判断其间0的个数是否<=k;
	2.O(n^2)[l,r]和[l,r+1]的联系很紧密，只需判断a[r+1]就可O(1)转移
	3.O(n)取尺法（two_pointer），O(n)遍历，右端点0的个数>k 时移动左端点到0的个数<=k 
trigger:
	
note:
	*
record:

date:
	2019.09.05
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dwn(i,a,b) for(int i=a;i>=b;--i) 
template <typename T> inline void rd(T &x){x=0;char c=getchar();int f=0;while(!isdigit(c)){f|=c=='-';c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}x=f?-x:x;} 
inline void write(int n){if(n==0)return;write(n/10);putchar(n%10+'0');}
#define mem(a,b) memset(a,b,sizeof(a))
#define ee(i,u) for(int i=head[u];i;i=e[i].next)

const int N = 3e5+10;

int n,k,cnt,ans;
int a[N];
bool vis[N];

#undef int
int main(){
#define int long long
	#ifdef WIN32
	freopen("","r",stdin);
	#endif
	rd(n),rd(k);
	rep(i,1,n)rd(a[i]);
	for(int i=1,j=1;i<=n;++i){
		if(a[i]==0){
			cnt++;
			vis[i]=1;
		}
		while(cnt>k && j<i){
			if(a[j]==0)cnt--;
			vis[j]=0;
			j++;
		}
		ans=max(i-j+1,ans);
	}
	printf("%lld
",ans);
	rep(i,1,n)printf("%lld ",vis[i]?1:a[i]);
	return 0;
}
/*
7 1 
1 0 0 1 1 0 1
*/
/*
4 
1 0 0 1 1 1 1
*/
/*
10 2 
1 0 0 1 0 1 0 1 0 1
*/
/*
5 
1 0 0 1 1 1 1 1 0 1
*/
//多组解任意输出一种