最佳植树距离 - 华为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
题解
这道题属于二分查找与贪心算法相结合的问题，目的是通过二分查找来确定适合种植树木的最大最小间距。
解题思路
- 数据结构选择:
- 采用一个数组
locs存储可种植的点坐标，并对该数组进行排序，便于后续计算。- 二分查找:
- 间距的范围在1到
(最大坐标 - 最小坐标)之间。通过二分查找确定能种下所有树苗的最大最小间距。- 在二分查找的过程中，每次计算一个中间值
mid，然后检查以此间距mid能否种下所有的树苗。- 贪心判断:
- 对于每个给定的间距
mid，从最左侧的可种植位置开始，贪心地选择每次尽量离上一个种植点最远的位置进行种植。如果种下的树苗数量达到要求，则返回true。- 输出:
- 最后输出通过二分查找找到的最大间距。
代码复杂度
- 时间复杂度: 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(mid, locs, szt)) {
left = mid; // 可以种下 szt 棵树，尝试更大的间距
} else {
right = mid; // 间距太大，尝试更小的间距
}
}
// 输出最大的合适间距
System.out.println(left);
}
// 判断间距为 x 时能否种下 szt 棵树苗
public static boolean ok(int x, int[] locs, int szt) {
// prev 表示上一棵树的位置，cnt 表示已种的树数量
int prev = locs[0], cnt = 1;
for (int cur : locs) {
if (cur - prev >= x) { // 当前距离符合间距要求则在当前位置种下一棵树
cnt++;
prev = cur;
}
}
return cnt >= szt; // 如果能种下足够数量的树苗则返回 true
}
}
Python
# 适合种树的坐标数量
n = int(input())
# 适合种树的坐标位置
locs = list(map(int, input().split()))
locs.sort()
# 树苗的数量
szt = int(input())
def ok(x:int) -> bool:
''' 种植间距为x 时能否种下 szt 颗树苗'''
global locs, szt
# 上一颗种树的位置，已经种的树数量
prev, cnt = locs[0], 1
for cur in locs:
if cur - prev >= x: # 当前距离符合间距要求则在当前位置种下一棵树
cnt += 1
prev = cur
return cnt >= szt
left, right = 1, locs[-1] - locs[0] + 1
while left + 1 < right:
mid = (left + right) // 2
if ok(mid):
left = mid
else:
right = mid
print(left)
'''
7
1 5 3 6 10 7 13
3
'''
# AC
C++
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// 种植间距为x 时能否种下 szt 颗树苗
bool ok(int x, const vector<int>& locs, int szt)
{
// prev 表示上一棵树的位置，cnt 表示已种的树数量
int prev = locs[0], cnt = 1;
for (int cur : locs) {
if (cur - prev >= x) { // 当前距离符合间距要求则在当前位置种下一棵树
cnt++;
prev = cur;
}
}
return cnt >= szt; // 如果能种下足够数量的树苗则返回 true
}
int main()
{
// 适合种树的坐标数量
int n;
cin >> n;
// 适合种树的坐标位置
vector<int> locs(n);
for (int i = 0; i < n; i++) {
cin >> locs[i];
}
// 对坐标位置进行排序
sort(locs.begin(), locs.end());
// 树苗的数量
int szt;
cin >> szt;
// 二分查找的边界
int left = 1;
int right = locs[n - 1] - locs[0] + 1;
// 二分查找，找到最大的合适间距
while (left + 1 < right) {
int mid = (left + right) / 2;
if (ok(mid, locs, szt)) {
left = mid; // 可以种下 szt 棵树，尝试更大的间距
} else {
right = mid; // 间距太大，尝试更小的间距
}
}
// 输出最大的合适间距
cout << left << endl;
return 0;
}
整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
原文地址：https://blog.csdn.net/user_longling/article/details/142435618
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！