OD刷题笔记合集🔗

补种未成活胡杨

问题描述

近些年来，我国防沙治沙取得显著成果。某沙漠新种植 棵胡杨（编号 到 ），排成一排。一个月后，有 棵胡杨未能成活。现可补种胡杨 棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？

输入格式

输入共四行：

1. 第一行包含一个整数 ，表示总种植数量。
2. 第二行包含一个整数 ，表示未成活胡杨数量。
3. 第三行包含 个用空格分隔的整数，表示未成活胡杨的编号（按从小到大排列）。
4. 第四行包含一个整数 ，表示最多可以补种的数量。

输出格式

输出一个整数，表示最多的连续胡杨棵树。

样例输入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）。

数据范围

题解

滑动窗口+双指针

这道题目要求在给定条件下，通过补种胡杨树来获得最长的连续胡杨树序列。

解题思路如下：

1. 首先，将胡杨树的状态表示为一个长度为 N 的数组，其中 1 表示存活的树，0 表示未成活的树。

2. 使用滑动窗口（双指针）技术来解决这个问题：

   • 用两个指针 left 和 right 表示当前考虑的区间。
   • 移动 right 指针扩大窗口，直到窗口内未成活的树木数量超过 K。
   • 记录当前窗口大小，这可能是一个潜在的最大连续序列。
   • 如果窗口内未成活的树木数量超过了 K，移动 left 指针缩小窗口，直到未成活的树木数量再次不超过 K。

3. 在整个过程中，持续更新最大连续树木数量。

参考代码

以下是五种语言的实现，每种实现都包含详细的注释：

• 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 ma