题目分析

小明需要在一条直线上种植树苗，目标是让这些树苗尽量均匀分布，以提高防沙效果。题目给定了若干适合种树的位置坐标，以及树苗的数量。需要找到一种种植方案，使树苗之间的最小间距尽可能大。

解题思路

1. 排序位置坐标：

   • 先对位置坐标排序，从小到大排列，便于计算间距并通过贪心地分配树苗，找到最优解。

2. 二分查找最小间距：

   • 使用二分查找来确定树苗之间的最大化最小间距。
   • 定义间距的左右边界 left 和 right：
     • left 初始化为 1，即最小可能的间距。
     • right 初始化为首尾位置的最大距离 positions[n-1] - positions[0]，即所有点的最大跨度。
   • 在 left 和 right 之间进行二分查找，选择一个中间间距 mid，并判断是否可以在至少 mid 间距下种植 m 棵树苗。

3. 检查函数 Check(d)：

   • 设计一个检查函数 Check(d)，用来判断是否可以在间距 d 的条件下，放置 m 棵树苗：
     • 以第一个位置放置第一棵树苗，然后顺序检查后续位置是否与上一个放置位置间距至少为 d。
     • 如果满足间距条件，则放置树苗并更新上一个放置位置。
     • 最后，若成功放置了 m 棵树苗，说明 d 是可行间距。
   • 该函数可以通过一次遍历位置坐标，在 O(n) 时间内完成检查。

4. 调整搜索边界：

   • 如果当前间距 mid 可行，则可以尝试更大的间距，将 left 移到 mid。
   • 否则，将 right 移到 mid - 1，尝试更小的间距。
   • 二分查找结束时，right 即为满足条件的最大最小间距。

复杂度分析

• 时间复杂度：

  • 对位置进行排序的时间复杂度为 O(n log n)。
  • 二分查找的迭代次数为 O(log(maxDistance))，其中 maxDistance 是首尾点间的距离。
  • 每次检查函数 Check(d) 需要遍历所有位置，时间复杂度为 O(n)。
  • 因此，总时间复杂度为 O(n log n + n log(maxDistance))，其中 n log n 排序是主导因素。

• 空间复杂度：

  • 额外的空间复杂度为 O(1)，主要用于二分查找和变量存储。

本质分析

本题的本质在于最大化最小值，属于经典的“跳跃间距优化”问题，可以通过二分查找结合贪心策略解决。二分查找用来确定一个目标间距，而检查函数用来验证该间距是否满足条件。

代码

Cpp

#include <bits/stdc++.h>
using namespace std;

int numPositions, numSeedlings;
vector<int> positions;

// 检查是否可以以间距 minDistance 放置所有树苗
bool Check(int minDistance) {
    int seedlingsToPlace = numSeedlings - 1; // 还需要放置的树苗数量
    int lastPosition = positions[0]; // 上次放置树苗的位置

    for (int i = 1; i < numPositions; i++) {
        if (positions[i] - lastPosition >= minDistance) { // 如果当前间距满足 minDistance
            seedlingsToPlace--;         // 放置一个树苗，减少待放置树苗数量
            lastPosition = positions[i]; // 更新上次放置的位置
        }
        if (seedlingsToPlace <= 0) return true; // 如果所有树苗都已放置，返回 true
    }
    return false; // 如果无法以 minDistance 间距放置所有树苗，返回 false
}

int main() {
    // 输入适合种树的坐标数量
    cin >> numPositions;
    positions.resize(numPositions);
    
    // 输入每个适合种树的位置坐标
    for (int i = 0; i < numPositions; i++) {
        cin >> positions[i];
    }

    // 对坐标位置进行排序，确保在一条直线上依次放置
    sort(positions.begin(), positions.end());
    
    // 输入树苗数量
    cin >> numSeedlings;
    
    int left = 1, right = positions[numPositions - 1] - positions[0]; // 初始化二分查找的边界
    
    // 二分查找找到最佳最小种植间距
    while (left < right) {
        int midDistance = (left + right + 1) / 2;
        if (Check(midDistance)) {
            left = midDistance; // 如果间距 midDistance 可行，尝试更大的间距
        } else {
            right = midDistance - 1; // 如果间距 midDistance 不可行，尝试更小的间距
        }
    }

    // 输出最佳的最小种植间距
    cout << right << endl;
    return 0;
}

Java

以下是将该C++代码转换为Java的版本：

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

public class Main {

    static int numPositions, numSeedlings;
    static int[] positions;

    // 检查是否可以以间距 minDistance 放置所有树苗
    static boolean check(int minDistance) {
        int seedlingsToPlace = numSeedlings - 1; // 还需要放置的树苗数量
        int lastPosition = positions[0]; // 上次放置树苗的位置

        for (int i = 1; i < numPositions; i++) {
            if (positions[i] - lastPosition >= minDistance) { // 如果当前间距满足 minDistance
                seedlingsToPlace--; // 放置一个树苗，减少待放置树苗数量
                lastPosition = positions[i]; // 更新上次放置的位置
            }
            if (seedlingsToPlace <= 0) return true; // 如果所有树苗都已放置，返回 true
        }
        return false; // 如果无法以 minDistance 间距放置所有树苗，返回 false
    }

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

        // 输入适合种树的坐标数量
        numPositions = scanner.nextInt();
        positions = new int[numPositions];

        // 输入每个适合种树的位置坐标
        for (int i = 0; i < numPositions; i++) {
            positions[i] = scanner.nextInt();
        }

        // 对坐标位置进行排序，确保在一条直线上依次放置
        Arrays.sort(positions);

        // 输入树苗数量
        numSeedlings = scanner.nextInt();

        int left = 1, right = positions[numPositions - 1] - positions[0]; // 初始化二分查找的边界

        // 二分查找找到最佳最小种植间距
        while (left < right) {
            int midDistance = (left + right + 1) / 2;
            if (check(midDistance)) {
                left = midDistance; // 如果间距 midDistance 可行，尝试更大的间距
            } else {
                right = midDistance - 1; // 如果间距 midDistance 不可行，尝试更小的间距
            }
        }

        // 输出最佳的最小种植间距
        System.out.println(right);
    }
}

Python

def check(min_distance):
    seedlings_to_place = num_seedlings - 1  # 还需要放置的树苗数量
    last_position = positions[0]  # 上次放置树苗的位置

    for i in range(1, num_positions):
        if positions[i] - last_position >= min_distance:  # 如果当前间距满足 min_distance
            seedlings_to_place -= 1  # 放置一个树苗，减少待放置树苗数量
            last_position = positions[i]  # 更新上次放置的位置
        if seedlings_to_place <= 0:
            return True  # 如果所有树苗都已放置，返回 True
    return False  # 如果无法以 min_distance 间距放置所有树苗，返回 False

# 输入适合种树的坐标数量
num_positions = int(input())
positions = list(map(int, input().split()))

# 对坐标位置进行排序，确保在一条直线上依次放置
positions.sort()

# 输入树苗数量
num_seedlings = int(input())

left, right = 1, positions[-1] - positions[0]  # 初始化二分查找的边界

# 二分查找找到最佳最小种植间距
while left < right:
    mid_distance = (left + right + 1) // 2
    if check(mid_distance):
        left = mid_distance  # 如果间距 mid_distance 可行，尝试更大的间距
    else:
        right = mid_distance - 1  # 如果间距 mid_distance 不可行，尝试更小的间距

# 输出最佳的最小种植间距
print(right)

题目内容

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

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

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

输入描述

第 $1$ 行表示适合种树的坐标数量

第 $2$ 行是适合种树的坐标位置

第 $3$ 行是树苗的数量

输出描述

最佳的最小种植间距

备注

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

样例1

输入

7
1 5 3 6 10 7 13
3

输出

6

说明

$3$ 棵树苗分别种植在 $1$，$7$，$13$ 位置时，树苗种植的最均匀，最小间距为 $6$