E卷-(100分)补种未成活胡杨

补种未成活胡杨

问题描述

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

输入格式

输入共四行：

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

输出格式

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

样例输入1

样例输出1

样例解释1

补种到 2 或 4 结果一样，最多的连续胡杨棵树都是 3。

样例输入2

样例输出2

样例解释2

补种第 7 棵树，最多连续胡杨树棵数为 6（5、6、7、8、9、10）。

数据范围

$1 \leq N \leq 100000$
$1 \leq M \leq N$
$0 \leq K \leq M$

题解

滑动窗口+双指针

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

解题思路如下：

首先，将胡杨树的状态表示为一个长度为 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())

#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());
    }
}

#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#

OD刷题笔记文章被收录于专栏

本专栏收集并整理了一些刷题笔记