您当前的位置: 首页 >  游戏

高校俱乐部

暂无认证

  • 3浏览

    0关注

    674博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

一个好玩的编程小游戏——最长全1区间

高校俱乐部 发布时间:2019-07-22 14:11:53 ,浏览量:3

题目:

给定一个长度为n的,仅包含0,1的数列。例如1,0,0,1,1,1,0。我们可以轻易算出,它的最长全1区间长度是3。从数组的第4位到第6位。

现在,你获得了k次可以将某个位置上的0变为1的机会,但可以不用完所有的机会。

请你给出,你使用了你的变化机会后,这个数列的最长全1区间最大是多少 分析:

要使最大全1区间最长,一定是将某段连续区间内的0变为1。由此,可从左到右扫描整个数组,记录每个位置向右依次将0变为1后的最大全1区间长度。最后求整个数组的最大值。 上代码:

a = input().split()
b = input().split()
n, k = int(a[0]), int(b[0])
alist = [int(x) for x in b]
#n, k = 4, 1
#alist = [0, 1, 0, 1]
 
maxlen = []
end = 0        # 指向全1区间的结尾
start = 0        # 指向全1区间的开头
 
while end < n:                      # 结束条件:end扫到末尾
    # 找到当前start对应的end的最远位置
    while k >= 0 and end < n:
        if alist[end] == 1:         # 如果是1,继续走
            end += 1
            continue
        k -= 1                      # 如果是0,消耗一次0到1的变化机会
        end += 1
    maxlen.append(end - start)      # 记录此时的最长全1区间
    
    # start向前挪动一位
    if alist[start] == 0:           # 如果挪动前start是0,则可节省1次01变化
        k = 1
    start += 1
print(max(maxlen))
关注
打赏
1656064541
查看更多评论
立即登录/注册

微信扫码登录

0.0394s