题解：AT_tkppc2016_c 有給休暇（Paid Vacation）

GYHL · 2024-03-14 21:51:12 · 题解

题目大意

一个有 n 个数字的数串只有 0 和 1，能把任意 k 个 0 变为 1，求最多有几个连续的 1。

思路

利用前缀和，就可知道某段到某段有几个是 0 的数，再枚举左端点和右端点，可最大为 100000，太大了，会超时，就可以用一个变量作为左端点，枚举右端点，如果这一段 0 的个数超过 k，这一段就不符合要求，就移动左端点，缩小这一段的长度，统计符合条件的最大值。

#include<bits/stdc++.h>
using namespace std;
int n,k,a[100005],x,s,t,ma,l,sum;//ma是答案,l是左端点,sum是左端点到右端点的距离
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>t;
        a[i]=a[i-1];
        if(t==0) a[i]++;//前缀和统计0的个数
    }
    for(int i=1;i<=n;i++){
        if(a[i]-a[l]<=k)
        {
            sum++;//如符合条件,距离加1,因为右端点一直在变
            ma=max(ma,sum);
        }
        else
        {
            ma=max(ma,sum),l++;//如不符合条件,左端点往后移
        }
     }

    cout<<ma;
    return 0;
}

时间复杂度：O(n)。