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

333次阅读
没有评论

共计 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);
    }
}
正文完
 0
裴先生
版权声明:本站原创文章,由 裴先生 2022-05-01发表,共计961字。
转载说明:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
本站勉强运行: