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], 1for cur in locs:if cur - prev >= x: # 当前距离符合间距要求则在当前位置种下一棵树cnt += 1prev = curreturn cnt >= sztleft, right = 1, locs[-1] - locs[0] + 1
while left + 1 < right:mid = (left + right) // 2if ok(mid):left = midelse:right = midprint(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;
}整理题解不易， 如果有帮助到您，请给点个赞 ❤️ 和收藏 ⭐，让更多的人看到。🙏🙏🙏
