补种未成活胡杨

题目描述

近些年来, 我国防沙治沙取得显著成果. 某沙漠新种植N棵胡杨 (编号1-N), 排成一排.

一个月后, 有M棵胡杨未能成活.

现可补种胡杨K棵, 请问如何补种 (只能补种, 不能新种), 可以得到最多的连续胡杨树?

输入描述

• N 总种植数量, 1 <= N <= 100000
• M 未成活胡杨数量, M 个空格分隔的数, 按编号从小到大排列, 1 <= M <= N
• K 最多可以补种的数量, 0 <= K <= M

输出描述

最多的连续胡杨棵树.

示例1

输入:

5
2
2 4
1

输出:

3

说明: 补种到2或4结果一样, 最多的连续胡杨棵树都是3.

示例2

输入:

10
3
2 4 7
1

输出:

6

说明: 种第7棵树, 最多连续胡杨树棵数位6 (5, 6, 7, 8, 9, 10)

题解

Python

def main():
    # 先读取输入值
    # 种树的数量
    total = int(input())
    # 树树的数量
    dead_count = int(input())
    # 死树的位置
    dead_list = list(map(int, input().split()))
    # 补种的数量 k
    k = int(input())
    assert len(dead_list) == dead_count

    # 树的生死状态
    # 0 表示存活, 1 表示不存活
    states = [0] * total

    # 更新树的状态
    # 注意这里是从1开始计数的, 要转换成从0开始计数
    for dead in dead_list:
        states[dead - 1] = 1

    # 双指针法
    left = 0
    right = 0
    # 最大连续存活的树的数量
    max_alive = 0
    # 窗口左侧边界经过的死树的数量
    dead_left = 0
    # 窗口右侧边界经过的死树的数量
    dead_right = 0

    # 遍历所有的树
    while right < total:
        # 更新窗口右侧经过的死树的数量
        dead_right += states[right]

        # 如果窗口内死树的数量比能补种的数量多, 就将窗口左侧往右移
        while dead_right - dead_left > k:
            dead_left += states[left]
            left += 1

        # 更新最大连续活着的树的数量
        max_alive = max(max_alive, right - left + 1)
        right += 1

    print(max_alive)

if __name__ == "__main__":
    main()