【OD真题】补种未成活胡杨[100分]

一、题目描述

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

二、输入描述

N 总种植数量
M 未成活胡杨数量
M 个空格分隔的数，按编号从小到大排列
K 最多可以补种的数量

其中：
1 <= N <= 100000
1 <= M <= N
0 <= K <= M

三、输出描述

3.1 示例 1

• 输入

5
2
2 4
1

• 输出

3

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

3.2 示例 2

• 输入

10
3
2 4 7
1

• 输出

6

说明
补种第 7 棵树，最多的连续胡杨棵树为 6（5,6,7,8,9,10）。

四、代码实现

4.1 方案一

    public int replantPoplar(int n, int m, String l, int k) {
        String[] deadArr = l.split(" ");
        int[] dead = Arrays.stream(deadArr).mapToInt(Integer::parseInt).toArray();
        int max = 0;
        for (int i = k - 1; i < m; i++) {
            // i为补种的最后一棵胡杨下标
            if (i == k - 1) {
                // 种最前面的k棵树
                max = Math.max(max, dead[k] - 1);
            } else if (i == m - 1) {
                // 种最后面的k棵树
                max = Math.max(max, n - dead[i - k]);
            } else {
                // 种中间的k棵树
                max = Math.max(max, dead[i + 1] - dead[i - k] - 1);
            }
        }
        return max;
    }

五、测试

    @Test
    void replantPoplar() {
        int max = day09.replantPoplar(5, 2, "2 4", 1);
        Assertions.assertEquals(3, max);

        max = day09.replantPoplar(10, 3, "2 4 7", 1);
        Assertions.assertEquals(6, max);
    }