烟台h5网站开发简洁大方的网站首页

烟台h5网站开发,简洁大方的网站首页,北京网站设计公司价格,wordpress商业授权价格题目链接#xff1a;1870. 准时到达的列车最小时速#xff08;中等#xff09; 算法原理#xff1a; 解法#xff1a;二分查找 50ms击败73.54% 时间复杂度O(n log(max_speed))#xff08;n 是 dist 数组长度#xff0c;max_speed ≈ 10^9 题目有两个变化的条件#xf…题目链接1870. 准时到达的列车最小时速中等算法原理解法二分查找50ms击败73.54%时间复杂度O(n × log(max_speed))n 是 dist 数组长度max_speed ≈ 10^9题目有两个变化的条件时速和时间且呈负相关单调时速↑ 花费时间↓ 由于要找最小时速属于在二分区间最左端点因此采用最左端点模型①目标变量时速②目标条件经过n趟车后花费的总时间hour③转换逻辑n趟车按此时速行驶后花费多少时间具体步骤①确定区间边界left1因为题目规定了hour≥1如果初始化为0相当于原地不动了right10⁷因为题目明确说了“测试用例保证答案不超过 10⁷”②确定模型呈负相关单调时速↑ 花费时间↓题目要求返回最小正整数时速因此采用最左端点模型注意虽然时间是double类型的但却不是浮点二分因为咱们要返回的是时速题目要求最小正整数时间的double是用来判断时速是否符合要求的③check方法设计累加各趟车需要花费的时间注意前n-1趟车的时间需要向上取整因为题目说了每趟列车只在整点发车而向上取整的公式在下面这篇博客应用过第 175 场双周赛Q2——3824. 减小数组使其满足条件的最小 K 值直接拿来用就可以最后一趟车的时间直接累加无需向上取整如果时间太长超过了hour说明时速太慢需要提速向右调整因此返回true④无法准时到达的情况由于每趟车只在整点发车不管你跑多快都得等到整点走因此最快的情况也得是dist.length-1个小时如果hour比这个小那么一定无法到达返回-1Java代码class Solution { public int minSpeedOnTime(int[] dist, double hour) { int left1,right10_000_000; //边界预处理每段至少一小时若hour不够直接返回-1 if(hourdist.length-1) return -1; while(leftright){ int midleft(right-left)/2; if(check(mid,dist,hour)) leftmid1; else rightmid; } return left; } private boolean check(int mid,int[] dist, double hour){ double time0; int ndist.length; for(int i0;in;i){ //只有前n-1段需要向上取整最后一段直接累加 if(i!n-1) time(double)((dist[i]-1)/mid1); else time(double)dist[i]/mid; //如果超时了说明速度太慢要提速向右移动所以返回true if(timehour) return true; } return timehour; } }