题目描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植 N 棵胡杨（编号 1-N），排成一排。

一个月后，有 M 棵胡杨未能成活。

现可补种胡杨 K 棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入描述

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

输出描述

输出最多的连续胡杨树棵数。

样例

输入1：

5
2
2 4
1

输出1：

3

输入2：

10
3
2 4 7
1

输出2：

6

题解思路

问题分析

这个问题可以转换为一个滑动窗口问题，我们要找到一段连续的胡杨树的区间，最多包含 K 棵可以补种的死树，并且这段区间的长度最大。

• 我们可以通过一个布尔数组记录每棵树是否死亡。这样，滑动窗口可以快速判断当前窗口内死树的数量。
• 使用双指针（滑动窗口）的技术，维护一个左指针和右指针的区间，在右指针逐步右移的同时，如果窗口内的死树数量超过了 K，那么就将左指针向右移动，直到死树数量不超过 K。

算法步骤

1. 初始化：

   • 用一个布尔数组 vis 来标记每棵树是否死亡。True 表示存活，False 表示死亡。
   • 初始化两个指针 left 和 right，分别指向窗口的左右边界，max_len 用于记录最大的连续存活树数，dead_count 用于记录当前窗口内死亡树的数量。

2. 遍历树的位置：

   • 对于每个右指针的位置 right，判断该位置的树是否死亡，如果死亡则 dead_count 加 1。
   • 如果窗口内死亡树的数量大于 K，则左指针逐步右移，直到死亡树数量小于等于 K。
   • 每次计算当前窗口的长度，更新 max_len。

3. 结束：

   • 当遍历完成后，max_len 即为最多连续存活的树的数量。

时间复杂度

• 初始化 vis 数组的时间复杂度为 O(N)。
• 遍历所有树的过程中，滑动窗口的操作复杂度为 O(N)，因此总的时间复杂度为 O(N)。

代码实现

Python 实现

def max_consecutive_trees(N, M, dead_trees, K):
    # 创建一个布尔数组，标记每棵树是否死亡
    vis = [True] * (N + 1)
    
    # 将死树标记为 False
    for tree in dead_trees:
        vis[tree] = False
    
    left = 0  # 滑动窗口的左边界
    max_len = 0  # 存储最大连续树的长度
    dead_count = 0  # 当前窗口内死树的数量
    
    # 遍历每一棵树的位置
    for right in range(1, N + 1):
        # 如果当前树死亡，增加死树数量
        if not vis[right]:
            dead_count += 1
        
        # 如果死树数量超过 K，左指针右移，直到死树数量不超过 K
        while dead_count > K:
            if not vis[left + 1]:
                dead_count -= 1
            left += 1
        
        # 更新最大连续树的长度
        max_len = max(max_len, right - left)
    
    return max_len

# 输入读取部分
N = int(input())  # 总树的数量
M = int(input())  # 死树的数量
dead_trees = [int(x) for x in input().split()]  # 死树的位置
K = int(input())  # 最多可以补种的死树数量

# 调用函数并输出结果
print(max_consecutive_trees(N, M, dead_trees, K))

Java 实现

import java.util.*;

public class Main {
    public static int maxConsecutiveTrees(int N, int M, int[] deadTrees, int K) {
        boolean[] vis = new boolean[N + 1];  // 创建一个布尔数组标记每棵树是否死亡
        Arrays.fill(vis, true);  // 默认所有树都存活
        for (int tree : deadTrees) {
            vis[tree] = false;  // 死树标记为 false
        }

        int left = 0, maxLen = 0, deadCount = 0;
        for (int right = 1; right <= N; right++) {
            // 如果当前树死亡，增加死树数量
            if (!vis[right]) {
                deadCount++;
            }

            // 如果死树数量超过 K，左指针右移，直到死树数量不超过 K
            while (deadCount > K) {
                if (!vis[left + 1]) {
                    deadCount--;
                }
                left++;
            }

            // 更新最大连续树的长度
            maxLen = Math.max(maxLen, right - left);
        }
        return maxLen;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();  // 总树的数量
        int M = sc.nextInt();  // 死树的数量
        int[] deadTrees = new int[M];
        for (int i = 0; i < M; i++) {
            deadTrees[i] = sc.nextInt();
        }
        int K = sc.nextInt();  // 最多可以补种的死树数量

        // 调用函数并输出结果
        System.out.println(maxConsecutiveTrees(N, M, deadTrees, K));
    }
}

C++ 实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int maxConsecutiveTrees(int N, int M, vector<int>& deadTrees, int K) {
    vector<bool> vis(N + 1, true);  // 创建一个布尔数组标记每棵树是否死亡
    for (int tree : deadTrees) {
        vis[tree] = false;  // 死树标记为 false
    }

    int left = 0, maxLen = 0, deadCount = 0;
    for (int right = 1; right <= N; right++) {
        // 如果当前树死亡，增加死树数量
        if (!vis[right]) {
            deadCount++;
        }

        // 如果死树数量超过 K，左指针右移，直到死树数量不超过 K
        while (deadCount > K) {
            if (!vis[left + 1]) {
                deadCount--;
            }
            left++;
        }

        // 更新最大连续树的长度
        maxLen = max(maxLen, right - left);
    }
    return maxLen;
}

int main() {
    int N, M, K;
    cin >> N >> M;
    vector<int> deadTrees(M);
    for (int i = 0; i < M; i++) {
        cin >> deadTrees[i];
    }
    cin >> K;

    // 调用函数并输出结果
    cout << maxConsecutiveTrees(N, M, deadTrees, K) << endl;
    return 0;
}

题目描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植$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）$