【算法题】补种未成活胡杨

共计 961 个字符，预计需要花费 3 分钟才能阅读完成。

import java.util.Scanner;

/**
 * 标题：补种未成活胡杨 | 时间限制：1秒 | 内存限制：262144K
 * 近些年来，我国防沙治沙取得显著成果。某沙漠新种植N棵胡杨（编号1-N），排成一排。一个月后，有M棵胡杨未能成活。
 * 现可补种胡杨K棵，请问如何补种（只能补种，不能新种），可以得到最多的连续胡杨树？
 * 输入描述:
 * N 总种植数量 1<=N<=100000 M 未成活胡杨数量 1<=M<=N M 个空格分隔的数，按编号从小到大排列 K 最多可以补种的数量 0<=K<=M
 * 输出描述:
 * 最多的连续胡杨棵树
 * 示例1
 * 输入
 * 5
 * 2
 * 2 4
 * 1
 * 输出
 * 3
 * 说明
 * 补种到2或4结果一样，最多的连续胡杨棵树都是3
 * 示例2
 * 输入
 * 10
 * 3
 * 2 4 7
 * 1
 * 输出
 * 6
 * 说明
 * 补种第7棵树，最多的连续胡杨棵树为6(5,6,7,8,9,10)
 *
 * @since 2022年5月1日
 */
public class M_N_T_19 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.nextLine());
        int M = Integer.parseInt(scanner.nextLine());

        String[] Ms = scanner.nextLine().split(" ");
        int[] ints_M = new int[M];
        for (int i = 0; i < Ms.length; i++) {
            ints_M[i] = Integer.parseInt(Ms[i]);
        }

        int K = Integer.parseInt(scanner.nextLine());

        // 开始补种 滑动窗口，首先知道补种也必须是连续的才有可能获得最大连续棵树，然后设定左右指针，保证中间有K棵树补种
        int max = 0;
        for (int i = 0; i <= ints_M.length - K; i++) {
            int le = 0;
            int ri = N;
            if (i > 0) {
                le = ints_M[i - 1];
            }

            if (i + K < ints_M.length) {
                ri = ints_M[i + K] - 1;
            }

            int temp = ri - le;
            if (temp > max) {
                max = temp;
            }
        }

        System.out.println(max);
    }
}