E卷-(100分)补种未成活胡杨
OD刷题笔记合集🔗
补种未成活胡杨
问题描述
近些年来，我国防沙治沙取得显著成果。某沙漠新种植 棵胡杨（编号
到
），排成一排。一个月后，有
棵胡杨未能成活。现可补种胡杨
棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
输入格式
输入共四行：
- 第一行包含一个整数
，表示总种植数量。
- 第二行包含一个整数
，表示未成活胡杨数量。
- 第三行包含
- 第四行包含一个整数
，表示最多可以补种的数量。
输出格式
输出一个整数，表示最多的连续胡杨棵树。
样例输入1
5
2
2 4
1
样例输出1
3
样例解释1
补种到 2 或 4 结果一样，最多的连续胡杨棵树都是 3。
样例输入2
10
3
2 4 7
1
样例输出2
6
样例解释2
补种第 7 棵树，最多连续胡杨树棵数为 6（5、6、7、8、9、10）。
数据范围
题解
滑动窗口+双指针
这道题目要求在给定条件下，通过补种胡杨树来获得最长的连续胡杨树序列。
解题思路如下：
-
首先，将胡杨树的状态表示为一个长度为 N 的数组，其中 1 表示存活的树，0 表示未成活的树。
-
使用滑动窗口（双指针）技术来解决这个问题：
- 用两个指针 left 和 right 表示当前考虑的区间。
- 移动 right 指针扩大窗口，直到窗口内未成活的树木数量超过 K。
- 记录当前窗口大小，这可能是一个潜在的最大连续序列。
- 如果窗口内未成活的树木数量超过了 K，移动 left 指针缩小窗口，直到未成活的树木数量再次不超过 K。
-
在整个过程中，持续更新最大连续树木数量。
参考代码
以下是五种语言的实现，每种实现都包含详细的注释：
- Python
def max_continuous_trees():
# 读取输入
N = int(input())
M = int(input())
dead_trees = list(map(int, input().split()))
K = int(input())
# 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
trees = [1] * (N + 1)
# 标记死亡的树
for tree in dead_trees:
trees[tree] = 0
left = right = 1 # 滑动窗口的左右指针
zeros = 0 # 当前窗口内 0 的数量
max_length = 0 # 最大连续树木数量
# 滑动窗口
for right in range(1, N + 1):
if trees[right] == 0:
zeros += 1
# 如果窗口内的 0 超过了可补种数量，移动左指针
while zeros > K:
if trees[left] == 0:
zeros -= 1
left += 1
# 更新最大连续树木数量
max_length = max(max_length, right - left + 1)
return max_length
# 计算并输出结果
print(max_continuous_trees())
- C
#include <stdio.h>
#include <stdlib.h>
int max(int a, int b) {
return a > b ? a : b;
}
int max_continuous_trees() {
int N, M, K;
scanf("%d", &N);
scanf("%d", &M);
// 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
int* trees = (int*)calloc(N + 1, sizeof(int));
for (int i = 1; i <= N; i++) {
trees[i] = 1;
}
// 标记死亡的树
for (int i = 0; i < M; i++) {
int dead_tree;
scanf("%d", &dead_tree);
trees[dead_tree] = 0;
}
scanf("%d", &K);
int left = 1, right = 1; // 滑动窗口的左右指针
int zeros = 0; // 当前窗口内 0 的数量
int max_length = 0; // 最大连续树木数量
// 滑动窗口
for (right = 1; right <= N; right++) {
if (trees[right] == 0) {
zeros++;
}
// 如果窗口内的 0 超过了可补种数量，移动左指针
while (zeros > K) {
if (trees[left] == 0) {
zeros--;
}
left++;
}
// 更新最大连续树木数量
max_length = max(max_length, right - left + 1);
}
free(trees);
return max_length;
}
int main() {
printf("%d\n", max_continuous_trees());
return 0;
}
- Javascript
const readline = require('readline');
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout
});
let N, M, K;
let dead_trees = [];
let lineCount = 0;
function max_continuous_trees() {
// 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
const trees = new Array(N + 1).fill(1);
// 标记死亡的树
for (let tree of dead_trees) {
trees[tree] = 0;
}
let left = 1, right = 1; // 滑动窗口的左右指针
let zeros = 0; // 当前窗口内 0 的数量
let max_length = 0; // 最大连续树木数量
// 滑动窗口
for (right = 1; right <= N; right++) {
if (trees[right] === 0) {
zeros++;
}
// 如果窗口内的 0 超过了可补种数量，移动左指针
while (zeros > K) {
if (trees[left] === 0) {
zeros--;
}
left++;
}
// 更新最大连续树木数量
max_length = Math.max(max_length, right - left + 1);
}
return max_length;
}
rl.on('line', (input) => {
lineCount++;
if (lineCount === 1) {
N = parseInt(input);
} else if (lineCount === 2) {
M = parseInt(input);
} else if (lineCount === 3) {
dead_trees = input.split(' ').map(Number);
} else if (lineCount === 4) {
K = parseInt(input);
console.log(max_continuous_trees());
rl.close();
}
});
- Java
import java.util.Scanner;
public class Main {
public static int maxContinuousTrees() {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int M = scanner.nextInt();
// 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
int[] trees = new int[N + 1];
for (int i = 1; i <= N; i++) {
trees[i] = 1;
}
// 标记死亡的树
for (int i = 0; i < M; i++) {
int deadTree = scanner.nextInt();
trees[deadTree] = 0;
}
int K = scanner.nextInt();
int left = 1, right = 1; // 滑动窗口的左右指针
int zeros = 0; // 当前窗口内 0 的数量
int maxLength = 0; // 最大连续树木数量
// 滑动窗口
for (right = 1; right <= N; right++) {
if (trees[right] == 0) {
zeros++;
}
// 如果窗口内的 0 超过了可补种数量，移动左指针
while (zeros > K) {
if (trees[left] == 0) {
zeros--;
}
left++;
}
// 更新最大连续树木数量
maxLength = Math.max(maxLength, right - left + 1);
}
return maxLength;
}
public static void main(String[] args) {
System.out.println(maxContinuousTrees());
}
}
- Cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int maxContinuousTrees() {
int N, M, K;
cin >> N >> M;
// 创建一个长度为 N+1 的数组，初始化为全 1（所有树都活着）
vector<int> trees(N + 1, 1);
// 标记死亡的树
for (int i = 0; i < M; i++) {
int deadTree;
cin >> deadTree;
trees[deadTree] = 0;
}
cin >> K;
int left = 1, right = 1; // 滑动窗口的左右指针
int zeros = 0; // 当前窗口内 0 的数量
int maxLength = 0; // 最大连续树木数量
// 滑动窗口
for (right = 1; right <= N; right++) {
if (trees[right] == 0) {
zeros++;
}
// 如果窗口内的 0 超过了可补种数量，移动左指针
while (zeros > K) {
if (trees[left] == 0) {
zeros--;
}
left++;
}
// 更新最大连续树木数量
maxLength = max(maxLength, right - left + 1);
}
return maxLength;
}
int main() {
cout << maxContinuousTrees() << endl;
return 0;
}
OD刷题笔记 文章被收录于专栏
本专栏收集并整理了一些刷题笔记
投递思源智通等公司10个岗位 >