题目描述
近些年来，我国防沙治沙取得显著成果。某沙漠新种植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
- 2
- 3
- 4
输出
3
- 1
说明 补种到2或4结果一样，最多的连续胡杨棵树都是3。
用例2
输入
10
3
2 4 7
1
- 1
- 2
- 3
- 4
输出
6
- 1
说明 补种第7棵树，最多连续胡杨树棵数位6（5，6，7，8，9，10）
python思路：
-
解题思路：
-
初始化树木状态： 我们首先将树木的状态表示为一个长度为 n 的数组 trees，其中 1 表示树木存活，0 表示树木已经死亡。输入的
dead_indices 数组给出了死亡树木的位置（是 1-based 的，需要转化成 0-based）。滑动窗口： 我们使用两个指针 left 和 right 来表示当前考虑的连续区间。right 指针从左到右遍历整个数组，left
指针表示当前区间的左边界。我们维护一个 zeros_count 来记录当前窗口内死树的数量。窗口调整： 每当窗口中的死树数量超过了 k，我们就移动 left 指针来缩小窗口，直到死树的数量不超过
k。每次更新窗口时，我们记录当前窗口的长度，并更新最大长度 max_length。返回结果： 遍历完整个数组后，max_length 就是我们能找到的最大长度的连续区域。
-
关键点：
-
滑动窗口算法： 本算法通过维护一个动态变化的窗口，能够在 O(n) 时间复杂度内找到最长的符合条件的区间。 边界条件处理：
在处理 dead_indices 时，注意数组是 1-based，而 Python 数组是 0-based，所以我们需要进行转换。 -
时间复杂度分析：
时间复杂度： 由于每个元素最多被 left 或 right 指针遍历一次，因此时间复杂度是 O(n)，其中 n
是树木的数量。 空间复杂度： 我们使用了一个长度为 n 的数组来表示树木状态，因此空间复杂度是 O(n)。
python解法：
def max_continuous_trees(n, m, dead_indices, k):
# 将死树的索引转化为集合，以便快速查找
dead_set = set(dead_indices)
# 初始化树木数组，默认所有树木都是活的（1表示活树）
trees = [1] * n
# 将死树位置置为0
for index in dead_indices:
trees[index - 1] = 0 # dead_indices是1-based，所以我们要减去1使其变为0-based
max_length = 0 # 记录最大连续区域的长度
left = 0 # 左指针
zeros_count = 0 # 记录当前窗口内的死树数量
# 遍历整个数组，right是右指针
for right in range(n):
if trees[right] == 0: # 如果当前树木是死树
zeros_count += 1 # 死树数量加1
# 如果当前窗口内的死树数量超过了k，调整左指针
while zeros_count > k:
if trees[left] == 0: # 如果左边界是死树
zeros_count -= 1 # 死树数量减1
left += 1 # 移动左指针，缩小窗口
# 更新最大连续区域长度
max_length = max(max_length, right - left + 1)
return max_length # 返回最大连续区间的长度
if __name__ == "__main__":
# 读取输入数据
n = int(input()) # 树木总数
m = int(input()) # 死树的数量
dead_indices = list(map(int, input().split())) # 死树的位置列表
k = int(input()) # 允许的最大死树数量
# 计算结果并输出
result = max_continuous_trees(n, m, dead_indices, k)
print(result)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
java解法：
import java.util.Arrays;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// 创建Scanner对象用于输入
Scanner sc = new Scanner(System.in);
// 输入数组的大小
int size = sc.nextInt();
// 输入最多允许的零的个数
int toRemove = sc.nextInt();
// 创建并初始化数组，所有元素初始为1
int[] arr = new int[size];
Arrays.fill(arr, 1);
// 输入并设置数组中要置为零的索引位置
for (int i = 0; i < toRemove; i++) {
int index = sc.nextInt() - 1; // 输入的索引是从1开始，减去1转为0基索引
arr[index] = 0; // 将该索引位置的元素置为零
}
// 输入最多允许的零的个数
int maxZeros = sc.nextInt();
// 调用findMaxSubarray函数计算结果并输出
System.out.println(findMaxSubarray(arr, maxZeros));
}
// findMaxSubarray方法用于找到符合条件的最长子数组
public static int findMaxSubarray(int[] arr, int maxZeros) {
// 左指针，初始化为0
int left = 0;
// 当前窗口中零的个数
int zeroCount = 0;
// 最大子数组的长度
int maxLength = 0;
// 右指针，遍历数组
for (int right = 0; right < arr.length; right++) {
// 如果当前元素为零，零的数量增加
if (arr[right] == 0) {
zeroCount++;
}
// 当零的个数超过maxZeros时，收缩窗口
while (zeroCount > maxZeros) {
// 如果左边的元素是零，减少零的数量
if (arr[left] == 0) {
zeroCount--;
}
// 移动左指针，缩小窗口
left++;
}
// 更新最大子数组的长度
maxLength = Math.max(maxLength, right - left + 1);
}
// 返回最大的子数组长度
return maxLength;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
c++解法：
#include - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
js解法：
// 引入 readline 模块，用于从标准输入获取用户输入
const readline = require("readline");
// 创建一个 readline 接口，用于处理输入和输出
const rl = readline.createInterface({
input: process.stdin, // 标准输入
output: process.stdout, // 标准输出
});
// 用于存储输入的各行数据
const inputs = [];
// 监听输入的每一行数据
rl.on("line", (input) => {
// 将每行输入保存到 inputs 数组中
inputs.push(input);
// 当输入的行数达到4行时，表示输入已完成
if (inputs.length === 4) {
// 解析输入数据
const total = parseInt(inputs[0], 10); // 树的总数
const deadCount = parseInt(inputs[1], 10); // 死树的数量
const deadPositions = inputs[2].split(" ").map(Number); // 死树的位置数组
const maxReplant = parseInt(inputs[3], 10); // 最大可重新种植的死树数
// 调用 findMaxConsecutive 函数来计算结果
const result = findMaxConsecutive(total, deadPositions, maxReplant);
// 输出计算结果
console.log(result);
// 清空 inputs 数组，准备处理下一个输入（如果有的话）
inputs.length = 0;
}
});
// 函数 findMaxConsecutive 用于寻找最长的连续子数组，子数组中最多可以有 k 个死树
function findMaxConsecutive(n, deadTrees, k) {
let leftPtr = 0; // 左指针，表示窗口的起始位置
let replantCnt = 0; // 当前窗口内的死树数量
let maxConsec = 0; // 最大的合法子数组长度
let deadPos = new Set(deadTrees); // 使用 Set 存储死树的位置，便于快速查找
// 遍历数组，使用 rightPtr 作为右指针，表示当前窗口的结束位置
for (let rightPtr = 0; rightPtr < n; rightPtr++) {
// 如果当前右指针指向的树是死树，增加死树计数
if (deadPos.has(rightPtr + 1)) {
replantCnt++;
}
// 如果当前窗口内的死树数量超过了允许的最大数量 k，移动左指针收缩窗口
while (replantCnt > k) {
// 如果左指针指向的是死树，减少死树计数
if (deadPos.has(leftPtr + 1)) {
replantCnt--;
}
// 移动左指针，缩小窗口
leftPtr++;
}
// 更新最大子数组的长度
maxConsec = Math.max(maxConsec, rightPtr - leftPtr + 1);
}
// 返回最大连续合法子数组的长度
return maxConsec;
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
c解法：
#include - 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
代码已自测，如您发现有未覆盖到的情况，欢迎私信或留言！ 会在看到的第一时间优化，感谢_！
评论记录：
回复评论：