D.二分查找－二分答案－求最小——1870. 准时到达的列车最小时速

题目链接：1870. 准时到达的列车最小时速（中等）

算法原理：

解法：二分查找

50ms击败73.54%

时间复杂度O(n × log(max_speed))（n 是 dist 数组长度，max_speed ≈ 10^9

题目有两个变化的条件：时速和时间，且呈负相关单调：时速↑ 花费时间↓ 由于要找最小时速，属于在二分区间最左端点，因此采用最左端点模型

①目标变量：时速

②目标条件：经过n趟车后花费的总时间<=hour

③转换逻辑：n趟车按此时速行驶后花费多少时间

具体步骤：

①确定区间边界：

left：1，因为题目规定了hour≥1，如果初始化为0，相当于原地不动了

right：10⁷，因为题目明确说了“测试用例保证答案不超过 10⁷”

②确定模型：呈负相关单调：时速↑ 花费时间↓，题目要求返回最小正整数时速，因此采用最左端点模型，注意虽然时间是double类型的，但却不是浮点二分，因为咱们要返回的是时速，题目要求最小正整数，时间的double是用来判断时速是否符合要求的

③check方法设计：累加各趟车需要花费的时间，注意前n-1趟车的时间需要向上取整，因为题目说了，每趟列车只在整点发车，而向上取整的公式在下面这篇博客应用过👇

第 175 场双周赛Q2——3824. 减小数组使其满足条件的最小 K 值

直接拿来用就可以，最后一趟车的时间直接累加，无需向上取整，如果时间太长，超过了hour，说明时速太慢，需要提速，向右调整，因此返回true

④无法准时到达的情况：由于每趟车只在整点发车，不管你跑多快，都得等到整点走，因此最快的情况也得是dist.length-1个小时，如果hour比这个小，那么一定无法到达，返回-1

Java代码：

class Solution { public int minSpeedOnTime(int[] dist, double hour) { int left=1,right=10_000_000; //边界预处理：每段至少一小时，若hour不够直接返回-1 if(hour<=dist.length-1) return -1; while(left<right){ int mid=left+(right-left)/2; if(check(mid,dist,hour)) left=mid+1; else right=mid; } return left; } private boolean check(int mid,int[] dist, double hour){ double time=0; int n=dist.length; for(int i=0;i<n;i++){ //只有前n-1段需要向上取整，最后一段直接累加 if(i!=n-1) time+=(double)((dist[i]-1)/mid+1); else time+=(double)dist[i]/mid; //如果超时了，说明速度太慢，要提速，向右移动，所以返回true if(time>hour) return true; } return time>hour; } }