美容 北京 公司 网站建设,曹县 做网站的公司,什么是网页开发,网站建设是程序员吗文章目录1. 题目2. 解题2.1 模拟超时2.2 二分查找1. 题目
给你一个浮点数 hour #xff0c;表示你到达办公室可用的总通勤时间。 要到达办公室#xff0c;你必须按给定次序乘坐 n 趟列车。 另给你一个长度为 n 的整数数组 dist #xff0c;其中 dist[i] 表示第 i 趟列车的行…
文章目录1. 题目2. 解题2.1 模拟超时2.2 二分查找1. 题目
给你一个浮点数 hour 表示你到达办公室可用的总通勤时间。 要到达办公室你必须按给定次序乘坐 n 趟列车。 另给你一个长度为 n 的整数数组 dist 其中 dist[i] 表示第 i 趟列车的行驶距离单位是千米。
每趟列车均只能在整点发车所以你可能需要在两趟列车之间等待一段时间。
例如第 1 趟列车需要 1.5 小时那你必须再等待 0.5 小时搭乘在第 2 小时发车的第 2 趟列车。 返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速单位千米每小时如果无法准时到达则返回 -1 。
生成的测试用例保证答案不超过 10^7 且 hour 的 小数点后最多存在两位数字 。
示例 1
输入dist [1,3,2], hour 6
输出1
解释速度为 1 时
- 第 1 趟列车运行需要 1/1 1 小时。
- 由于是在整数时间到达可以立即换乘在第 1 小时发车的列车。第 2 趟列车运行需要 3/1 3 小时。
- 由于是在整数时间到达可以立即换乘在第 4 小时发车的列车。第 3 趟列车运行需要 2/1 2 小时。
- 你将会恰好在第 6 小时到达。示例 2
输入dist [1,3,2], hour 2.7
输出3
解释速度为 3 时
- 第 1 趟列车运行需要 1/3 0.33333 小时。
- 由于不是在整数时间到达故需要等待至第 1 小时才能搭乘列车。第 2 趟列车运行需要 3/3 1 小时。
- 由于是在整数时间到达可以立即换乘在第 2 小时发车的列车。第 3 趟列车运行需要 2/3 0.66667 小时。
- 你将会在第 2.66667 小时到达。示例 3
输入dist [1,3,2], hour 1.9
输出-1
解释不可能准时到达因为第 3 趟列车最早是在第 2 小时发车。提示
n dist.length
1 n 10^5
1 dist[i] 10^5
1 hour 10^9
hours 中小数点后最多存在两位数字来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-speed-to-arrive-on-time 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目LeetCode 1231. 分享巧克力极小极大化 二分查找
2.1 模拟超时
51 / 53 个通过测试用例
class Solution {
public:int minSpeedOnTime(vectorint dist, double hour) {int n dist.size();if(n ceil(hour))return -1;long s 0;for(int i 0; i n; i)s dist[i];int v s/hour-1;if(v 0) v 1;while(1){double t 0;for(int i 0; i n-1; i){ t ceil(dist[i]/double(v));}t dist.back()/double(v);if(t hour)break;v;}return v;}
};2.2 二分查找
v 的增加总得到达时间不会变多具有单调性采用二分查找
class Solution {
public:int minSpeedOnTime(vectorint dist, double hour) {int n dist.size();if(n ceil(hour))return -1;int l 1, r 1e9, ans, v;while(l r){v (lr)1;double t 0;for(int i 0; i n-1; i)t ceil(dist[i]/double(v));t dist.back()/double(v);if(t hour){ans v;r v-1;}elsel v1;}return ans;}
};308 ms 98.8 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
