题目
题目描述：
题目背景：
近些年来，我国在沙漠治理方面取得了显著成就。某沙漠实验室在干旱地区实验性地种植了 𝑁 棵胡杨树，这些胡杨树排成一排，编号从 1 到 𝑁。由于环境恶劣，部分胡杨树未能成活。
任务：
现在实验室得到了 𝐾 棵补种树苗的预算，可以在任意未成活的位置进行补种。
请你计算，在补种不超过 𝐾 棵树苗的情况下，最多可以得到多少棵连续成活的胡杨树？
输入描述：
第一行输入一个整数 𝑁，代表胡杨的总种植数量。（1≤𝑁≤100000）
第二行输入一个整数 𝑀，代表未成活胡杨的数量。（1≤𝑀≤𝑁）
第三行输入 𝑀 个整数，代表未成活胡杨的编号（编号从小到大排列）。（1≤编号≤𝑁）
第四行输入一个整数 𝐾，代表可以补种的树苗数量。（0≤𝐾≤𝑀）
输出描述：
输出一个整数，代表补种后最多能够得到的连续成活胡杨树的数量。
示例：
示例1：
输入：
5
2
2 4
1
输出：
3
说明：
共有 5 棵树，编号 1, 2, 3, 4, 5。未成活的是 2 号和 4 号。
若补种 2 号，成活树变为 1, 2, 3，连续长度为 3。
若补种 4 号，成活树变为 3, 4, 5，连续长度为 3。
最大连续长度为 3。
示例 2：
输入：
10
3
2 4 7
1
输出：
6
说明：
正确逻辑：补种 7 号，连续成活范围为 3, 4(死), 5, 6, 7(补), 8, 9, 10，由于 4 号仍是死的，最长连续是 5, 6, 7, 8, 9, 10，长度为 6。
解题思路
这道题的核心思想是将“补种 𝐾 棵树”转化为在一个区间内寻找最多能容纳 𝐾 个“死树”的最长连续区间。
数据预处理：将原始的 𝑁 棵树看作一个数组，成活的标记为
1，未成活的标记为0。题目输入中通常只给出未成活树的编号，你需要将这些信息转换成一个方便处理的数组或列表，或者直接利用未成活树编号的有序性。双指针维护窗口：使用两个指针
left和right来定义一个窗口。right指针向右移动，不断扩大窗口。在窗口移动过程中，统计当前窗口内“死树”（标记为
0）的数量dead_count。
窗口收缩：当窗口内“死树”的数量
dead_count超过了允许补种的数量 𝐾 时，需要移动left指针来缩小窗口，直到dead_count重新小于或等于 𝐾 为止。记录最大值：在每次窗口扩大或收缩后，当前窗口的长度（
right - left + 1）就是一个可能的答案，取所有可能长度的最大值即为最终结果。
代码
常规解法：
package com.huaweiod.c.undo;
import java.util.Arrays;
import java.util.Scanner;
/**
* 补种未成活胡杨树
*/
public class ReplantingUnviablePopulusEuphratica {
public static int solution(int n, int[] deathIndexes, int k) {
// 1. 初始化树木状态：1为活，0为死
int[] trees = new int[n];
Arrays.fill(trees, 1);
for (int index : deathIndexes) {
// 题目编号从1开始，数组下标从0开始，所以需要 index - 1
trees[index - 1] = 0;
}
int left = 0;
int right = 0;
int deathCount = 0;
int maxLength = 0;
// 2. 标准滑动窗口模板
while (right < n) {
// 如果右边界是死树，增加当前窗口内的死树计数
if (trees[right] == 0) {
deathCount++;
}
// 3. 如果当前窗口内死树超过了补种预算 k，则收缩左边界
while (deathCount > k) {
if (trees[left] == 0) {
deathCount--;
}
left++;
}
// 4. 计算当前满足条件的窗口长度，更新最大值
maxLength = Math.max(maxLength, right - left + 1);
right++;
}
return maxLength;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
int[] deathIndexes = new int[m];
for (int i = 0; i < m; i++) {
deathIndexes[i] = sc.nextInt();
}
int k = sc.nextInt();
int length = solution(n, deathIndexes, k);
System.out.println(length);
}
}
进阶解法：
我们可以将未成活的树编号看作一段段“围栏”的边界。补种 𝐾 棵树，相当于在死树编号序列中，抹掉连续 𝐾 个死树节点，计算抹掉后左右两侧成活树能连通的最大跨度。
为了方便处理边界，我们在死树编号列表的最左边添加一个虚拟编号 0，最右边添加一个虚拟编号 N+1。
package com.huaweiod.c.completed;
import java.util.Scanner;
/**
* 补种胡杨树进阶版
*/
public class PopulusEuphraticaAdvanced {
/*
* 滑动窗口操作死树坐标：
*
* 窗口代表补种 k 棵树后覆盖的死树区间。
* 假设我们补种从 deadPos[i] 到 deadPos[i+k-1] 这 k 棵树。
* 那么这组连续成活树的最左端受 deadPos[i-1] 限制，最右端受 deadPos[i+k] 限制。
* 连续长度 = (右边界编号) - (左边界编号) - 1
* 简化为 = deadPos[i+k] - deadPos[i-1] - 1
*/
public static int solution(int n, int[] deadPos, int k) {
int maxLength = 0;
for (int i = 1; i + k < deadPos.length; i++) {
// i 是当前补种区间的第一个死树索引
// i + k 是补种完 k 棵后，遇到的第一个“依然死着”的树索引
int currentLength = deadPos[i + k] - deadPos[i - 1] - 1;
maxLength = Math.max(maxLength, currentLength);
}
return maxLength;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 输入处理
int n = sc.nextInt(); // 总数
int m = sc.nextInt(); // 死树数
// 只存死树位置，并补充虚拟边界
int[] deadPos = new int[m + 2];
deadPos[0] = 0; // 虚拟左边界
for (int i = 0; i < m; i++) {
deadPos[i] = sc.nextInt();
}
deadPos[m + 1] = n + 1; // 虚拟右边界
// 补种预算
int k = sc.nextInt();
// 特殊情况
if (k >= m) {
System.out.println(n);
return;
}
System.out.println(solution(n, deadPos, k));
}
}
评论