【华为OD题库-002】最佳植树距离-Java

题目

小明在直线的公路上种树，现在给定可以种树的坑位的数星和位置，以及需要种多少棵树苗，问树苗之间的最小间距是多少时，可以保证种的最均匀（两棵树苗之间的最小间距最大)
输入描述
输入三行:
第一行一个整数:坑位的数量
第二行以空格分隔的数组:坑位的位置
第三行一个整数:需要种植树苗的数量
输出描述
树苗之间的最小间距
示例1:
输入∶
7
1 3 6 7 8 11 13
3
输出:
6
三颗树苗分别种在1、7、13的位置，可以保证种的最均匀，树苗之间的最小间距为6。

思路

可以使用二分法解决。为了便于描述，设输入的数组为arr，坑位数量为n，需要种植的数为x。
先将arr从小到大排序
两棵树之前的最小间距是L=1，最大间距R=arr[n-1]-arr[0]。
先看最小间距ans取mid=(L+R)/2时，是否可以种下x棵树。如果可以种下，因为要求ans的最大值，那么小于mid时的情况都不用考虑，直接左边界L取mid+1；如果取mid时，种不下x棵树，那么mid右边的肯定更加种不下，右边界R直接取mid-1;通过上述思路，不断缩小查找边界，即可找到最大的ans。
现在的问题在于，对于给定最小间距，怎么判断是否种得下X棵树。已示例数据为例，我们的坑位是：[1，3，6，7，8，11，13]。假设最小间距是4。种树量为cnt。遍历坑位：
假定在1种第一棵树，cnt=1；
3距1的距离是2，小于4，不种；
6距1的距离是5，大于4，种植，cnt=2，后续遍历时就应该以6为参照物；
7距6为1，不种；
8距6位2，不种；
11距6为4,种植，cnt=3，后续以11为参照物；
13距11为2，不种;
遍历结束，所以最小间距是4时，在[1，3，6，7，8，11，13]这种坑位下，最多种3棵树。怎么判断是否种得下X棵树？只需要3>=x即可。
还有一个问题，二分法判断时，while (l <? r)，此处是否取等呢？应该要取等，当l==r时，根据上述逻辑，我们会再判断一次mid，即l是否满足条件，满足的话ans最后就会取到l，然后l等于mid+1,结束二分查找。我们举一个例子更能说明情况，假设坑位是1 3 5 7，要种植的树木x是2，执行上述逻辑：
初始状态，l=1,r=6,mid=3,checked(3)时，可以在1,5种2棵树，满足（等于x），l=mid+1=4
l=4,r=6,mid=5,checked(5)时，可以在1,7种2棵树，满足，l=mid+1=6
l=6,r=6，此时如果判定边界不取等，那么就结束二分查找了得到的结果就是5，显然不对。应该在左右边界在相等时，继续判断一次，最后得到结果6。

题解

package hwod;import java.util.Arrays;
import java.util.Scanner;public class PlantTree {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int m = sc.nextInt();int[] grids = new int[m];for (int i = 0; i < m; i++) {grids[i] = sc.nextInt();}int n = sc.nextInt();System.out.println(maxDistance(grids, n));}private static int maxDistance(int[] grids, int n) {Arrays.sort(grids);int l = 1, r = grids[grids.length - 1] - grids[0], ans = -1;while (l <= r) {int mid = l + r >> 1;if (checked(mid, grids, n)) {ans = mid;l = mid + 1;} else {r = mid - 1;}}return ans;}private static boolean checked(int mid, int[] grids, int n) {int pre = grids[0],cnt=1;for (int i = 1; i < grids.length; i++) {if (grids[i] - pre >= mid) {pre = grids[i];cnt++;}}return cnt >= n;}}