最佳植树距离 - 华为OD统一考试(E卷)

2024华为OD机试（C卷+D卷+E卷）最新题库【超值优惠】Java/Python/C++合集

题目描述

按照环保公司要求，小明需要在沙化严重的地区进行植树防沙工作，初步目标是种植一条直线的树带。由于有些区域目前不适合种植树木，所以只能在一些可以种植的点来种植树木。

在树苗有限的情况下，要达到最佳效果，就要尽量散开种植，不同树苗之间的最小间距要尽量大。给你一个适合种植树木的点坐标和一个树苗的数量，请帮小明选择一个最佳的最小种植间距。

例如，适合种植树木的位置分别为1,3,5,6,7,10,13 树苗数量是3，种植位置在1,7,13，树苗之间的间距都是6，均匀分开，就达到了散开种植的目的，最佳的最小种植间距是6

输入描述

第1行表示适合种树的坐标数量
第2行是适合种树的坐标位置
第3行是树苗的数量
例如：
7
1 3 5 6 7 10 13
3

输出描述

最佳的最小种植问距

补充说明

位置范围为1~ 10000000，种植树苗的数量范围2 ~ 10000000，用例确保种植的树苗数量不会超过有效种植坐标数量。

示例1

输入：
7
1 3 5 6 7 10 13
3

输出：
6

题解

这道题属于二分查找与贪心算法相结合的问题，目的是通过二分查找来确定适合种植树木的最大最小间距。

解题思路

1. 数据结构选择:
   • 采用一个数组locs存储可种植的点坐标，并对该数组进行排序，便于后续计算。
2. 二分查找:
   • 间距的范围在1到(最大坐标 - 最小坐标)之间。通过二分查找确定能种下所有树苗的最大最小间距。
   • 在二分查找的过程中，每次计算一个中间值mid，然后检查以此间距mid能否种下所有的树苗。
3. 贪心判断:
   • 对于每个给定的间距mid，从最左侧的可种植位置开始，贪心地选择每次尽量离上一个种植点最远的位置进行种植。如果种下的树苗数量达到要求，则返回true。
4. 输出:
   • 最后输出通过二分查找找到的最大间距。

代码复杂度

• 时间复杂度: O(N * log(D)) ，其中N是坐标数量，D是坐标范围（locs[n-1] - locs[0]）。
• 空间复杂度: O(N) ，主要用于存储可种植点的数组。

Java

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author code5bug
 */
public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 适合种树的坐标数量
        int n = scanner.nextInt();
        // 适合种树的坐标位置
        int[] locs = new int[n];
        for (int i = 0; i < n; i++) {
            locs[i] = scanner.nextInt();
        }
        // 对坐标位置进行排序
        Arrays.sort(locs);

        // 树苗的数量
        int szt = scanner.nextInt();

        // 二分查找的边界
        int left = 1;
        int right = locs[n - 1] - locs[0] + 1;

        // 二分查找，找到最大的合适间距
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (ok(m