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

· · 题解

借鉴了Ethan812820的题解，但是代码是我自己写出来的，思路也更清晰一些。

题目大意

给你 n 个数，问如何将这 n 个数中的 k 个 0 变成 1，使最长的连续一段 1 的数量最多。

具体思路

考虑使用双指针。两个分支：

  1. 若还能继续将 0 变为 1，即 k \ne 0，则尝试将第 r 个数变成 1。当然，如果第 r 个数本来就是 1，就不需要减少次数。但是如果第 r 个数为 0，需要减少次数，要将 k 减一，最后 r 加一，别忘了更新 ans。
  2. 若不能继续将 0 变为 1，即 k = 0，则尝试将第 l 个数变回原来的样子，如果第 l 个数原本就是 1。k 不变，如果第 l 个数原来是 0，要把变化的次数加回去，k 加一，最后 l 加一。

完整代码

代码来咯！

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
long long a[100005],sum,ans,l=1,r=0;
int main(){
    int n,k;
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];//读入a[i]。 
    }
    while(r<=n){
        if(sum<=k){//如果变换的次数小于等于k。 
            ans=max(r-l+1,ans);//判断是否需要更新ans。 
            r++;//右指针+1。 
            if(a[r]==0) sum++;//变换的次数+1。 
        }
        else{
            if(a[l]==0) sum--;//变换的次数-1。 
            l++;//左指针+1。 
        }
    }
    cout<<ans;
    return 0;
}

时间复杂度 O(n)，应该是优于二分的，而且比较好想。
感谢观看！