建设银行客户投诉网站,高端seo服务,用php做购物网站视频,微信小程序界面设计模板这道题是一个典型的算法题#xff0c;涉及计算在限制的时间内列车速度的最小值。这是一个优化问题#xff0c;通常需要使用二分查找来求解。
题目描述#xff08;中等#xff09;
准时到达的列车最小时速 给你一个浮点数 hour #xff0c;表示你到达办公室可用的总通勤时…这道题是一个典型的算法题涉及计算在限制的时间内列车速度的最小值。这是一个优化问题通常需要使用二分查找来求解。
题目描述中等
准时到达的列车最小时速 给你一个浮点数 hour 表示你到达办公室可用的总通勤时间。要到达办公室你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist 其中 dist[i] 表示第 i 趟列车的行驶距离单位是千米。
每趟列车均只能在整点发车所以你可能需要在两趟列车之间等待一段时间。
例如第 1 趟列车需要 1.5 小时那你必须再等待 0.5 小时搭乘在第 2 小时发车的第 2 趟列车。 返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速单位千米每小时如果无法准时到达则返回 -1 。
生成的测试用例保证答案不超过 107 且 hour 的 小数点后最多存在两位数字 。 题目大意
你需要乘坐 n 趟列车并且需要按给定的顺序乘坐。每趟列车都要在整点发车所以可能需要在两趟列车之间等待。你可以给定一个浮点数 hour作为你所能使用的最大通勤时间。需要找到一个最小的正整数速度使得总用时不超过给定的 hour无法达到则返回 -1。
解题思路
理解等待时间由于列车只能整点发车即使乘车时间不满整数小时也需要等到下一个整数小时。计算用时 对于前 n-1 趟列车必须在整点发车。其总时间为这些列车每趟到达所需时间的上限。最后一趟列车则直接计算实际用时因为它不需要等下一个整点发车。 二分查找 初始最小速度设为1最大速度设定为题目保证的上限或使用一个足够大的值。使用二分查找来找到使得总乘机时间不超过 hour 的最小整数速度。对于每个速度通过计算每趟列车旅游所消耗的时间来判断该速度是否符合条件。
C和C代码实现
C代码 bool canReachOnTime(const vectorint dist, double hour, int speed) {double totalTime 0.0;int n dist.size();for (int i 0; i n; i) {double timeNeeded static_castdouble(dist[i]) / speed;if (i n - 1) {totalTime timeNeeded; // Last train, no need to round up} else {totalTime ceil(timeNeeded); // Round up for all but the last train}}return totalTime hour;
}int minSpeedOnTime(const vectorint dist, double hour) {int left 1, right 1e7, minSpeed -1;while (left right) {int mid left (right - left) / 2;if (canReachOnTime(dist, hour, mid)) {minSpeed mid;right mid - 1;} else {left mid 1;}}return minSpeed;
}
C代码
由于C语言的math.h库并没有很好的支持浮点的ceil函数你可能需要手动编写这个功能。
#include stdio.h
#include math.hint canReachOnTime(int* dist, int distSize, double hour, int speed) {double totalTime 0.0;for (int i 0; i distSize; i) {double timeNeeded (double)dist[i] / speed;if (i distSize - 1) {totalTime timeNeeded; // Last train, no need to round up} else {totalTime ceil(timeNeeded); // Round up for all but the last train}}return totalTime hour;
}int minSpeedOnTime(int* dist, int distSize, double hour) {int left 1, right 10000000, minSpeed -1;while (left right) {int mid left (right - left) / 2;if (canReachOnTime(dist, distSize, hour, mid)) {minSpeed mid;right mid - 1;} else {left mid 1;}}return minSpeed;
}int main() {int dist[] {1, 3, 2};int n sizeof(dist) / sizeof(dist[0]);double hour 2.7;printf(Minimum speed required: %d\n, minSpeedOnTime(dist, n, hour));return 0;
}算法和代码分析
canReachOnTime函数这个辅助函数判断给定的速度下能否在限制时间内到达。它遍历所有列车计算总用时。对倒数第二趟列车使用ceil将乘车时间圆整至下一整数以模拟等待时间的影响。二分查找利用二分查找来优化最小的速度搜索将搜索空间从1到10000000每次通过中值检验是否满足时间条件不符合则增加速度范围符合则记录并尝试更小速度。复杂度二分查找的复杂度为O(log M)其中M为速度的搜索范围判断能否到达的复杂度为O(N)因此总复杂度为O(N log M)。
