做外贸的网站公司,海外求购信息网,苏州万浩伟网络科技有限公司,社交网站开发技术岗题目 小明在直线的公路上种树#xff0c;现在给定可以种树的坑位的数星和位置#xff0c;以及需要种多少棵树苗#xff0c;问树苗之间的最小间距是多少时#xff0c;可以保证种的最均匀#xff08;两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数…题目 小明在直线的公路上种树现在给定可以种树的坑位的数星和位置以及需要种多少棵树苗问树苗之间的最小间距是多少时可以保证种的最均匀两棵树苗之间的最小间距最大) 输入描述 输入三行: 第一行一个整数:坑位的数量 第二行以空格分隔的数组:坑位的位置 第三行一个整数:需要种植树苗的数量 输出描述 树苗之间的最小间距 示例1: 输入∶ 7 1 3 6 7 8 11 13 3 输出: 6 三颗树苗分别种在1、7、13的位置可以保证种的最均匀树苗之间的最小间距为6。 思路 可以使用二分法解决。为了便于描述设输入的数组为arr坑位数量为n需要种植的数为x。 先将arr从小到大排序 两棵树之前的最小间距是L1最大间距Rarr[n-1]-arr[0]。 先看最小间距ans取mid(LR)/2时是否可以种下x棵树。如果可以种下因为要求ans的最大值那么小于mid时的情况都不用考虑直接左边界L取mid1如果取mid时种不下x棵树那么mid右边的肯定更加种不下右边界R直接取mid-1;通过上述思路不断缩小查找边界即可找到最大的ans。 现在的问题在于对于给定最小间距怎么判断是否种得下X棵树。已示例数据为例我们的坑位是[136781113]。假设最小间距是4。种树量为cnt。遍历坑位 假定在1种第一棵树cnt1 3距1的距离是2小于4不种 6距1的距离是5大于4种植cnt2后续遍历时就应该以6为参照物 7距6为1不种 8距6位2不种 11距6为4,种植cnt3后续以11为参照物 13距11为2不种; 遍历结束所以最小间距是4时在[136781113]这种坑位下最多种3棵树。怎么判断是否种得下X棵树只需要3x即可。 还有一个问题二分法判断时while (l ? r)此处是否取等呢应该要取等当lr时根据上述逻辑我们会再判断一次mid即l是否满足条件满足的话ans最后就会取到l然后l等于mid1,结束二分查找。我们举一个例子更能说明情况假设坑位是1 3 5 7要种植的树木x是2执行上述逻辑 初始状态l1,r6,mid3,checked(3)时可以在1,5种2棵树满足等于xlmid14 l4,r6,mid5,checked(5)时可以在1,7种2棵树满足lmid16 l6,r6此时如果判定边界不取等那么就结束二分查找了得到的结果就是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],cnt1;for (int i 1; i grids.length; i) {if (grids[i] - pre mid) {pre grids[i];cnt;}}return cnt n;}}
