题解 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]);
}
```