首页 > 试题广场 > 最长全1串
[编程题]最长全1串

给你一个01字符串,定义答案=该串中最长的连续1的长度,现在你有至多K次机会,每次机会可以将串中的某个0改成1,现在问最大的可能答案


输入描述:
输入第一行两个整数N,K,表示字符串长度和机会次数

第二行输入N个整数,表示该字符串的元素

( 1 <= N <= 300000
, 0 <= K <= N )


输出描述:
输出一行表示答案
示例1

输入

10 2 
1 0 0 1 0 1 0 1 0 1

输出

5
双指针,一次遍历!博客有粗略的讲解:https://blog.csdn.net/weixin_42564710/article/details/98513244
n,k = list(map(int,raw_input().split()))
num = list(map(int,raw_input().split()))
i,j =0,0
res = 0
while j<n:
    if num[j]==1:
        j += 1
    elif k > 0:
        k -= 1
        j += 1
    else:
        res = max(res,j-i)
        while i<j and num[i]==1:
            i += 1
        j += 1
        i += 1
res = max(res,j-i)
print(res)



发表于 2019-08-05 20:10:42 回复(0)
暴力解的话,考虑以0~n-k的字符开头的最长字符串长度,求出最大的路径。因为以0开头的字符串必定不会是最大的字符串长度,所以可以只考虑以1开头的字符串。
发表于 2019-08-09 10:54:00 回复(0)
#include<bits/stdc++.h>
 
usingnamespacestd;
constintmaxn = 3e5+10;
 
intsum[maxn];
intmain()
{
    intn,k,x;
    cin>>n>>k;
    for(inti = 1; i <= n; i++)
    {
        cin>>x;
        sum[i] = sum[i-1] + x;
    }
    intl = 1, r = 1 , ans = 0;
    while(r <= n) // 双指针尺取法一下 左右区间推进一下就行了
    {
        if((r - l + 1) - (sum[r] - sum[l - 1]) <= k)// 总数减去1的个数就是0的个数
        {
            ans = max(ans,r - l + 1);r++;continue;
        }
        elseif(l < r) l++;
        else{l++;r++;}
    }
    cout<<ans<<endl;
    return0;
}

发表于 2019-05-29 22:45:44 回复(0)

66.66%

编辑于 2019-05-13 20:09:38 回复(0)
#include <iostream>
#include <cstdio>
using namespace std;
int n,m,tmp;
int main(){
    scanf("%d %d",&n,&m);
    int sum[n+1];
    sum[0]=0;
    for (int i=1;i<=n;++i) {
        scanf("%d",&tmp);
        sum[i]=sum[i-1]+tmp;
        //cout<<sum[i]<<endl;
    }
    int ans=m;
    int i=0,j;
    while (i<n){
        if (sum[i+1]-sum[i]>0){
            int j=ans+i;
            while (j<=n){
                if (j-i-sum[j]+sum[i]>m) break;
                ++j;
            }
            if (j!=n) --j;
            //cout<<j<<' '<<i<<endl;
            ans=max(ans,j-i);
        }
        ++i;
    }
    cout<<ans<<endl;
}

发表于 2019-05-09 15:30:22 回复(3)

热门推荐

通过挑战的用户

查看代码