华为OD机考2025A卷补种未成活胡杨真题解析
笔记哥 /
04-12 /
38点赞 /
0评论 /
106阅读
# 题目描述与示例
## 题目描述
近些年来，我国防沙治沙取得显著成果。某沙漠新种植`N`棵胡杨（编号`1-N`），排成一排。
一个月后，有`M`棵胡杨未能成活。
现可补种胡杨`K`棵，请问如何补种（只能补种，不能新种) ,可以得到最多的连续胡杨树?
题目练习网址：https://www.algomooc.com/problem/P3254
## 输入描述
```csharp
N`：总种植数量 `1<=N<=10``^5
M`：未成活胡杨数量 `1<=M<=N
```
`M`个空格分隔的数，按编号从小到大排列
```csharp
K`：最多可以补种的数量`0`` ``<=`` ``K`` ``<=`` ``M
```
## 输出描述
最多的连续胡杨棵树
## 示例一
### 输入
```Plain
5
2
2 4
1
```
### 输出
```Plain
3
```
### 说明
补种胡杨`2`或`4`，可以得到连续的胡杨`[1, 2, 3]`或`[3, 4, 5]`。
## 示例二
### 输入
```Plain
10
3
2 4 7
1
```
### 输出
```Plain
6
```
### 说明
补种胡杨`7`，可以得到连续的胡杨`[5, 6, 7, 8, 9, 10]`。
## 示例三
### 输入
```Plain
20
3
4 9 15
2
```
### 输出
```Plain
16
```
# 解题思路
## 不定滑窗解法
一种非常容易想到的做法是，对**原来给定的数据进行平铺还原的操作**。譬如对于示例二
```Plain
10
3
2 4 7
1
```
我们将这个长度为`10`的原数组平铺为
```Python
[1, 0, 1, 0, 1, 1, 0, 1, 1, 1]
```
其中`0`表示尚未种树，`1`表示已经种树。
>
>
> 注意，由于题目所给定的编号是`1-N`，而数组的下标是从`0`开始的，此处的编号会存在一个`1`的偏差。
>
这部分过程的代码如下
```Python
# 初始化平铺数组，初始化均为1
nums = [1] * N
# 遍历所有死树
for i in range(M):
# trees[i]是死树从1到N的编号
# trees[i]是死树在数组中从0到N-1的索引
nums[trees[i]-1] = 0
```
由于`k = 1`，这意味着我们只能够最多种下一棵树。种下的这棵树，要使得数组存在最长的连续的`1`。
所以问题就可以转变为，找到一个**最长的连续子数组**，这个子数组包含`k`个`0`。
因为这`k`个`0`都将会被替换为`1`，将得到最长的连续`1`的个数。
譬如对于示例二而言，我们仅需将索引为`6`的未成活杨树进行补种，就可以得到最长的连续`1`的数组。
```Python
[1, 0, 1, 0, 1, 1, 0, 1, 1, 1]
```
直接使用滑窗三问三答就很简单了
```Python
# 初始化左指针为0，初始化窗口中包含的0的个数为0，初始化答案为0
left = 0
win_0 = 0
ans = 0
# 进行滑窗过程
for right, num in enumerate(nums):
# A1
if num == 0:
win_0 += 1
# A2
while win_0 > K:
if nums[left] == 0:
win_0 -= 1
left += 1
# A3
ans = max(ans, right - left + 1)
print(ans)
```
注意到上述做法的时间复杂度是`O(N)`的，当`N`取上限值`10^5`时，是可以通过所有用例的。
## 固定滑窗解法
>
>
> 固定滑窗的解法较抽象，但是时间复杂度可以达到更加优秀的`O(M)`的复杂度。感兴趣的同学可以自行学习。
>
从题目所给的几个例子可以看出，如果`M`远小于`N`，**那么那些原先已经连续成活的树木，完全可以只用区间长度来进行表示**。
譬如对于示例二，由于我们知道为未成活的杨树编号分别为
```Python
2 4 7
```
那么也就知道，原先就已经成活的杨树被分成了`4`部分（`4`个区间），其中数目分别为
```Python
1 1 2 3
```
这样就比不定滑窗解法中，将原先的数组进行平铺出来的这种做法
```Python
[1, 0, 1, 0, 1, 1, 0, 1, 1, 1]
```
进行了更进一步的**数据压缩**。
这个结果可以用下面代码得到
```Python
# 构建tree_left哈希表用于表示某棵死树
# 与其左边最近的死树（上一棵死树）之间，一共有多少棵连续的活树
tree_left = dict()
# 第一棵死树为trees[0]，由于编号是从1开始
# 所以其左边一共有trees[0] - 1棵连续的活树
tree_left[trees[0]] = trees[0] - 1
# 遍历除了第一棵死树外的所有死树
for i in range(1, M):
# 当前死树，上一棵死树的编号分别为trees[i], trees[i-1]
tree, pre_tree = trees[i], trees[i-1]
# 两棵树之间的连续活树的数目为 tree - pre_tree - 1
tree_left[tree] = tree - pre_tree - 1
# 构建tree_right哈希表用于表示某棵死树
# 与其右边最近的死树（下一棵死树）的之间，一共有多少棵连续的活树
tree_right = dict()
# 最后一棵死树为trees[-1]，最后一棵树的编号为N
# 所以其右边一共有N - trees[-1]棵连续的活树
tree_right[trees[-1]] = N - trees[-1]
# 遍历除了最后一棵死树外的所有死树
for i in range(M-1):
# 当前死树，下一棵死树的编号分别为trees[i], trees[i+1]
tree, nxt_tree = trees[i], trees[i+1]
# 两棵树之间的连续活树的数目为 nxt_tree - tree - 1
tree_right[tree] = nxt_tree - tree - 1
```
其中`tree_left`表示，某个未成活杨树编号的左边，一共存在多少棵连续的活树。
同理`tree_right`表示，某个未成活杨树编号的右边，一共存在多少棵连续的活树。
譬如对于上述例子存在
```Python
tree_left = {
2: 1,
4: 1,
7: 2}
tree_right = {
2: 1,
4: 2,
7: 3}
```
由于每种下一棵树，能够使得每一个死树的左右两边的连续活树连接起来。
因此我们会考虑，如果将其中原先的`M`棵死树中的近邻的`K`棵进行种植，则可以尽可能长地得到连续的活树了。
这就退化成了一个固定滑窗的问题。
>
>
> 考虑原来的长度为`M`的死树数组`trees`，选择其中连续的`K`个元素将其转为活树，使得连续的活树数目尽可能的多。求最大的连续活树的数目。
>
显然，每一个固定滑窗中连续存活的活树数目由三部分构成：
1. 这`K`棵补种的活树
2. 这`K`棵补种的活树中的**最左边那棵补种的树，其左边连续的活树数目**
3. 这`K`棵补种的活树的每一棵树，其右边连续的活树数目
因此第一个固定滑窗的初始化为
```Python
win_sum = K + tree_left[trees[0]] + sum(tree_right[i] for i in trees[:K])
```
而每一次窗口移动的时候，最右边新补种的树的右边，要将加上`tree_right[right]`棵新种下的树。（A1）
而最左边原先补种的树不再种植，那么这部分原先存在窗口中的树`tree_left[left]`将被删去。（A2）
考虑固定滑窗三问三答，代码为
```Python
# 考虑第一个固定滑窗的情况，这个滑窗包含了最开始的K棵死树，如果把这些树都种下
# 第一个固定滑窗中的连续成活胡杨的数目由以下部分构成：
# 1. K棵补种的树
# 2. 第一棵死树trees[0]左边所有连续成活的树
# 3. 这K棵死树右边的连续成活的树
# 上述部分进行求和，即第一个固定滑窗的连续成活胡杨总和，用变量win_sum表示
win_sum = K + tree_left[trees[0]] + sum(tree_right[i] for i in trees[:K])
# 初始化答案变量为第一个固定滑窗的结果
ans = win_sum
# 进行固定滑窗过程
for right, idx in enumerate(trees[K:], K):
# Q1：对于每一个右指针right所指的元素idx，做什么操作？
# A1：将idx右边的连续成活胡杨，加入窗口和win_sum中
win_sum += tree_right[idx]
# Q2：对于left所指的元素idx_left，要做什么操作？
# A2：将idx_left左边的连续成活胡杨，从窗口和win_sum中减出
left = right-K
idx_left = trees[left]
win_sum -= tree_left[idx_left]
# Q3：如何更新ans？
# A3：取ans和win_sum中的较大值进行更新
ans = max(win_sum, ans)
```
# 代码
## 解法一：不定滑窗
### Python
```Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 胡杨总数
N = int(input())
# 未成活数目
M = int(input())
# 未成活胡杨的位置
trees = list(map(int, input().split()))
# 补种数目
K = int(input())
# 初始化平铺数组，初始化均为1
nums = [1] * N
# 初始化平铺数组，初始化均为1
nums = [1] * N
# 遍历所有死树
for i in range(M):
# trees[i]是死树从1到N的编号
# trees[i]-1是死树在数组中从0到N-1的索引
nums[trees[i]-1] = 0
# 初始化左指针为0，初始化窗口中包含的0的个数为0，初始化答案为0
left = 0
win_0 = 0
ans = 0
# 进行滑窗过程
for right, num in enumerate(nums):
# A1
if num == 0:
win_0 += 1
# A2
while win_0 > K:
if nums[left] == 0:
win_0 -= 1
left += 1
# A3
ans = max(ans, right - left + 1)
# 输出答案
print(ans)
```
### Java
```Java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
// 胡杨总数
int N = scanner.nextInt();
// 未成活数目
int M = scanner.nextInt();
// 未成活胡杨的位置
int[] trees = new int[M];
for (int i = 0; i < M; i++) {
trees[i] = scanner.nextInt();
}
// 补种数目
int K = scanner.nextInt();
// 初始化平铺数组，初始化均为1
int[] nums = new int[N];
for (int i = 0; i < N; i++) {
nums[i] = 1;
}
// 遍历所有死树
for (int i = 0; i < M; i++) {
// trees[i]是死树从1到N的编号
// trees[i]-1是死树在数组中从0到N-1的索引
nums[trees[i] - 1] = 0;
}
// 初始化左指针为0，初始化窗口中包含的0的个数为0，初始化答案为0
int left = 0;
int win_0 = 0;
int ans = 0;
// 进行滑窗过程
for (int right = 0; right < N; right++) {
// A1
if (nums[right] == 0) {
win_0++;
}
// A2
while (win_0 > K) {
if (nums[left] == 0) {
win_0--;
}
left++;
}
// A3
ans = Math.max(ans, right - left + 1);
}
// 输出答案
System.out.println(ans);
}
}
```
### C++
```C
#include
#include
using namespace std;
int main() {
// 胡杨总数
int N;
cin >> N;
// 未成活数目
int M;
cin >> M;
// 未成活胡杨的位置
vector trees(M);
for (int i = 0; i < M; i++) {
cin >> trees[i];
}
// 补种数目
int K;
cin >> K;
// 初始化平铺数组，初始化均为1
vector nums(N, 1);
// 遍历所有死树
for (int i = 0; i < M; i++) {
// trees[i]是死树从1到N的编号
// trees[i]-1是死树在数组中从0到N-1的索引
nums[trees[i] - 1] = 0;
}
// 初始化左指针为0，初始化窗口中包含的0的个数为0，初始化答案为0
int left = 0;
int win_0 = 0;
int ans = 0;
// 进行滑窗过程
for (int right = 0; right < N; right++) {
// A1
if (nums[right] == 0) {
win_0++;
}
// A2
while (win_0 > K) {
if (nums[left] == 0) {
win_0--;
}
left++;
}
// A3
ans = max(ans, right - left + 1);
}
// 输出答案
cout << ans << endl;
return 0;
}
```
### 时空复杂度
时间复杂度：`O(N)`。仅需一次遍历平铺后的数组，每一个元素只会被`right`和`left`遍历到至多`2`次。
空间复杂度：`O(1)`。仅需若干常数变量
## 解法二：固定滑窗
### Python
```Python
# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 胡杨总数
N = int(input())
# 未成活数目
M = int(input())
# 未成活胡杨的位置
trees = list(map(int, input().split()))
# 补种数目
K = int(input())
# 构建tree_left哈希表用于表示某棵死树
# 与其左边最近的死树（上一棵死树）之间，一共有多少棵连续的活树
tree_left = dict()
# 第一棵死树为trees[0]，由于编号是从1开始
# 所以其左边一共有trees[0] - 1棵连续的活树
tree_left[trees[0]] = trees[0] - 1
# 遍历除了第一棵死树外的所有死树
for i in range(1, M):
# 当前死树，上一棵死树的编号分别为trees[i], trees[i-1]
tree, pre_tree = trees[i], trees[i-1]
# 两棵树之间的连续活树的数目为 tree - pre_tree - 1
tree_left[tree] = tree - pre_tree - 1
# 构建tree_right哈希表用于表示某棵死树
# 与其右边最近的死树（下一棵死树）的之间，一共有多少棵连续的活树
tree_right = dict()
# 最后一棵死树为trees[-1]，最后一棵树的编号为N
# 所以其右边一共有N - trees[-1]棵连续的活树
tree_right[trees[-1]] = N - trees[-1]
# 遍历除了最后一棵死树外的所有死树
for i in range(M-1):
# 当前死树，下一棵死树的编号分别为trees[i], trees[i+1]
tree, nxt_tree = trees[i], trees[i+1]
# 两棵树之间的连续活树的数目为 nxt_tree - tree - 1
tree_right[tree] = nxt_tree - tree - 1
# 考虑第一个固定滑窗的情况，这个滑窗包含了最开始的K棵死树，如果把这些树都种下
# 第一个固定滑窗中的连续成活胡杨的数目由以下部分构成：
# 1. K棵补种的树
# 2. 第一棵死树trees[0]左边所有连续成活的树
# 3. 这K棵死树右边的连续成活的树
# 上述部分进行求和，即第一个固定滑窗的连续成活胡杨总和，用变量win_sum表示
win_sum = K + tree_left[trees[0]] + sum(tree_right[i] for i in trees[:K])
# 初始化答案变量为第一个固定滑窗的结果
ans = win_sum
# 进行固定滑窗过程
for right, idx in enumerate(trees[K:], K):
# Q1：对于每一个右指针right所指的元素idx，做什么操作？
# A1：将idx右边的连续成活胡杨，加入窗口和win_sum中
win_sum += tree_right[idx]
# Q2：对于left所指的元素idx_left，要做什么操作？
# A2：将idx_left左边的连续成活胡杨，从窗口和win_sum中减出
left = right-K
idx_left = trees[left]
win_sum -= tree_left[idx_left]
# Q3：如何更新ans？
# A3：取ans和win_sum中的较大值进行更新
ans = max(win_sum, ans)
print(ans)
```
### C++
```C
#include
#include
#include
using namespace std;
int main() {
int N, M, K;
cin >> N >> M; // 胡杨总数、未成活数目
vector trees(M); // 未成活胡杨的位置
for (int i = 0; i < M; i++) {
cin >> trees[i];
}
cin >> K; // 补种数目
unordered_map treeLeft; // 构建tree_left哈希表用于表示某棵死树
treeLeft[trees[0]] = trees[0] - 1; // 第一棵死树为trees[0]，由于编号是从1开始，所以其左边一共有trees[0] - 1棵连续的活树
for (int i = 1; i < M; i++) {
int tree = trees[i]; // 当前死树
int preTree = trees[i - 1]; // 上一棵死树的编号
treeLeft[tree] = tree - preTree - 1; // 两棵树之间的连续活树的数目为 tree - pre_tree - 1
}
unordered_map treeRight; // 构建tree_right哈希表用于表示某棵死树
treeRight[trees[M - 1]] = N - trees[M - 1]; // 最后一棵死树为trees[-1]，最后一棵树的编号为N，所以其右边一共有N - trees[-1]棵连续的活树
for (int i = 0; i < M - 1; i++) {
int tree = trees[i]; // 当前死树
int nxtTree = trees[i + 1]; // 下一棵死树的编号
treeRight[tree] = nxtTree - tree - 1; // 两棵树之间的连续活树的数目为 nxt_tree - tree - 1
}
int winSum = K + treeLeft[trees[0]]; // 考虑第一个固定滑窗的情况，这个滑窗包含了最开始的K棵死树，如果把这些树都种下
for (int i = 0; i < K; i++) {
winSum += treeRight[trees[i]]; // 第一个固定滑窗中的连续成活胡杨的数目由以下部分构成：1. K棵补种的树 2. 第一棵死树trees[0]左边所有连续成活的树 3. 这K棵死树右边的连续成活的树
}
int ans = winSum; // 初始化答案变量为第一个固定滑窗的结果
for (int right = K, left = 0; right < M; right++, left++) {
int idx = trees[right]; // 对于每一个右指针right所指的元素idx，将idx右边的连续成活胡杨，加入窗口和win_sum中
winSum += treeRight[idx];
int idxLeft = trees[left]; // 对于left所指的元素idxLeft，将idxLeft左边的连续成活胡杨，从窗口和win_sum中减出
winSum -= treeLeft[idxLeft];
ans = max(ans, winSum); // 更新ans，取ans和win_sum中的较大值进行更新
}
cout << ans << endl;
return 0;
}
```
## 时空复杂度
时间复杂度：`O(``M``)`。构建哈希表和滑窗过程，均需要遍历`M`棵未成活胡杨树。
空间复杂度：`O(``M``)`。两个哈希表所占空间。
本文来自投稿，不代表本站立场，如若转载，请注明出处：http//www.knowhub.vip/share/2/2182
- 热门的技术博文分享
- 1 . ESP实现Web服务器
- 2 . 从零到一：打造高效的金仓社区 API 集成到 MCP 服务方案
- 3 . 使用C#构建一个同时问多个LLM并总结的小工具
- 4 . .NET 原生驾驭 AI 新基建实战系列Milvus ── 大规模 AI 应用的向量数据库首选
- 5 . 在Avalonia/C#中使用依赖注入过程记录
- 6 . [设计模式/Java] 设计模式之工厂方法模式
- 7 . 5. RabbitMQ 消息队列中 Exchanges(交换机) 的详细说明
- 8 . SQL 中的各种连接 JOIN 的区别总结！
- 9 . JavaScript 中防抖和节流的多种实现方式及应用场景
- 10 . SaltStack 远程命令执行中文乱码问题
- 11 . 推荐10个 DeepSeek 神级提示词，建议搜藏起来使用
- 12 . C#基础：枚举、数组、类型、函数等解析
- 13 . VMware平台的Ubuntu部署完全分布式Hadoop环境
- 14 . C# 多项目打包时如何将项目引用转为包依赖
- 15 . Chrome 135 版本开发者工具（DevTools）更新内容
- 16 . 从零创建npm依赖，只需执行一条命令
- 17 . 关于 Newtonsoft.Json 和 System.Text.Json 混用导致的的序列化不识别的问题
- 18 . 大模型微调实战之训练数据集准备的艺术与科学
- 19 . Windows快速安装MongoDB之Mongo实战
- 20 . 探索 C# 14 新功能：实用特性为编程带来便利
- 相关联分享
- 华为OD机考2025A卷补种未成活胡杨真题解析