公司网站设计要求,上海到北京高铁票价多少,汽车工厂视频网站建设,做网站一般多钱目录 一、题目描述二、输入描述三、输出描述四、备注说明五、二分查找六、解题思路七、Java算法源码八、效果展示1、输入2、输出3、说明 一、题目描述
按照环保公司要求#xff0c;小明需要在沙化严重的地区进行植树防沙工作#xff0c;初步目标是种植一条直线的树带。
由于… 目录 一、题目描述二、输入描述三、输出描述四、备注说明五、二分查找六、解题思路七、Java算法源码八、效果展示1、输入2、输出3、说明 一、题目描述
按照环保公司要求小明需要在沙化严重的地区进行植树防沙工作初步目标是种植一条直线的树带。
由于有些区域目前不适合种植树木所以只能在一些可以种植的点来种植树木。 在树苗有限的情况下要达到最佳效果就要尽量散开种植不同树苗之间的最小间距要尽量大。
给你一个适合种情树木的点坐标和一个树苗的数量请帮小明选择一个最佳的最小种植间距。
例如适合种植树木的位置分别为1,3,5,6,7,10,13 树苗数量是3种植位置在1,7,13树苗之间的间距都是6均匀分开就达到了散开种植的目的最佳的最小种植间距是6。
二、输入描述
第1行表示适合种树的坐标数量。
第2行是适合种树的坐标位置。
第3行是树苗的数量。
三、输出描述
最佳的最小种植间距。
四、备注说明
位置范围为1~10000000
种植树苗的数量范围2~10000000
用例确保种植的树苗不会超过有效种植坐标数量
五、二分查找
二分查找Binary Search也称为折半查找是一种在有序数组中查找特定元素的搜索算法。
二分查找的基本思想是将数组分成两部分确定待查找元素可能存在的那一部分然后继续对该部分进行二分直到找到目标元素或者确定该元素不存在于数组中。
比如下面这段Java代码
public class BinarySearch { public static int binarySearch(int[] array, int target) { int left 0; int right array.length - 1; while (left right) { int mid (left right) / 2; if (array[mid] target) { return mid; } else if (array[mid] target) { left mid 1; } else { right mid - 1; } } return -1; } public static void main(String[] args) { int[] array {1, 3, 5, 7, 9}; int target 5; int result binarySearch(array, target); if (result -1) { System.out.println(Element not found); } else { System.out.println(Element found at index result); } }
}在这个示例中binarySearch方法接收一个有序数组array和要查找的目标元素target。然后使用循环进行二分查找将搜索范围不断缩小直到找到目标元素或确定该元素不存在于数组中。如果找到目标元素返回其索引否则返回-1。
在main方法中我们定义一个数组和一个目标元素然后调用binarySearch方法并打印结果。
六、解题思路
第一行输入种树的坐标数量第二行输入树的坐标位置通过java8 Stream表达式简洁/方便/上档次快速拆解输入行对树的坐标位置进行排序第三行输入树苗的数量通过二分查找进行比较取中间位置mid定义变量count记录植树的总棵数取第一棵树的位置遍历树的坐标位置arr并记录相对位置输出最佳的最小种植间距。
七、Java算法源码
// 树的坐标位置
public static int[] arr;
// 树苗的数量
public static int num;public static void main(String[] args) {Scanner sc new Scanner(System.in);// 种树的坐标数量int n Integer.valueOf(sc.nextLine());// 树的坐标位置arr Arrays.stream(sc.nextLine().split( )).mapToInt(Integer::parseInt).toArray();// 树苗的数量num Integer.valueOf(sc.nextLine());// 树的坐标位置排序Arrays.sort(arr);int min arr[0];int max arr[n - 1] - arr[0];// 通过二分查找进行比较while (min max) {// 取中间位置int mid (min max) / 2;if (compare(mid)) {min mid;} else {max mid - 1;}}System.out.println(max);
}public static boolean compare(int mid) {// 植树的总棵数int count 1;// 第一棵树的位置int curPos arr[0];for (int i 1; i arr.length; i) {if (arr[i] - curPos mid) {// 相距位置大于等于 mid则可以种树count;// 相对位置需要改变curPos arr[i];}}return count num;
}八、效果展示
1、输入
7 1 3 6 7 8 11 13 3
2、输出
6
3、说明
三颗树苗分别种在 1、7、13 的位置可以保证种的最均匀树苗之间的最小间距为 6。如果选择最小间距为 7则无法种下3颗树苗。 下一篇华为OD机试真题 Java 实现【简易内存池】【2023 B卷 200分 考生抽中题】
本文收录于华为OD机试JAVA真题A卷B卷
刷的越多抽中的概率越大每一题都有详细的答题思路、详细的代码注释、样例测试发现新题目随时更新全天CSDN在线答疑。
