题解 CF660C 【Hard Process】
引领天下
2019-01-28 22:18:16
看到C++的都是二分的尺取法表示不服
这题朴素想法：枚举l，r，暴力求[l,r]中0的个数是否小于k，复杂度$O(n^{3})$
我们想想有没有什么优化的办法
很明显，对于一个含0的区间，我们让区间中的0都填满是最优的
于是维护一段区间，保证区间中的0的个数≤k就可以
于是就可以对于0的个数≤k时右移右端点，增添新的位置，扩大区间；
当[l,r]中0的个数＞k时我们没有必要再回到l从头开始，可以只右移l，到[l,r]中0的个数≤k时为止（其实最后肯定=k，自己想想为什么！）
于是复杂度降到了线性的$O(n)$，或成此题最优解？
并不长的代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int a[300005],k,n,ans,cnt,ml,mr;
int main(){
scanf ("%d%d",&n,&k);
for (int i=1;i<=n;i++)scanf ("%d",&a[i]);
for (int l=1,r=1;r<=n;r++){//持续右移右端点
cnt+=!a[r];
if (cnt>k){
cnt-=!a[l];
l++;
}//长了就右移左端点
if (r-l+1>ans)ans=r-l+1,ml=l,mr=r;
}
for (;ml<=mr;ml++)a[ml]=1;
printf ("%d\n",ans);
for (int i=1;i<=n;i++)printf ("%d ",a[i]);
}
```