最长全1串

[编程题]最长全1串

热度指数：6378 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

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

数据范围：字符串长度满足 $1 \le n \le 300000 \$ ，保证输入的字符串只包含 0 和 1 ， $0 \le k \le n \$

输入描述:

输入第一行两个整数 n , k ，表示字符串长度和机会次数

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

输出描述:

输出一行表示答案

示例1

输入

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

输出

示例2

输入

10 5
1 0 0 1 0 1 0 1 0 1

输出

算法知识视频讲解

Python

sky游荡

这种题目还不熟练，就是那种一看很简单，一写全bug，然后半小时过去了，然后一小时过去了，然后。。。贼特么烦。

n,k = map(int,input().split())
ss = ''.join(input().split())
i,j,max_value = 0,0,0
while j<len(ss):
    if ss[j] =='1':
        j+=1
    elif k>0:
        k-=1
        j+=1       
    else:
        if ss[i]=='0':
            k+=1
            i+=1
        else:
            i+=1
    max_value = max(max_value,j-i)
print(max_value)

编辑于 2020-04-22 20:20:29 回复(0)