题解 CF660C 【Hard Process】

发表于 更新于 阅读次数： Waline：
CF660C 【Hard Process】题解。

看到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)$，或成此题最优解？

并不长的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#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]);
}