二分
单调性:列车的时速越快,花费的时间就越小。
什么情况是无法到达的呢?
从题意可以得知,就算列车的速度再快,除了最后一辆车,前面的车至少都要1小时,所以只需要判断列车的数量和向下取整后的总时间进行判断。
- 总时间hour向下取整,相当于忽略掉最后一辆车不用等的时间。
- 若总车数 - 1 > hour向下取整,则说明每辆车花费1小时都不能按时到达。
- 特判无法到达的情况
- 对于列车的时速进行二分
时间复杂度$O(NlogN)$,空间复杂度$O(1)$
AC代码
class Solution {
public:
double get(int sp, vector<int>& dist, double hour) {
double res = 0.0;
for (int i = 0 ; i < dist.size() ; i ++) {
int d = dist[i];
if (i == dist.size() - 1) res += d * 1.0 / sp;
else res += ceil(d * 1.0 / sp);
if (res > hour) return 1e10;
}
return res;
}
int minSpeedOnTime(vector<int>& dist, double hour) {
int n = dist.size(), h = (int) hour;
//特判无法到达的情况
if (n - 1 > h) return -1;
//二分
int l = 1, r = 1e9 + 1;
while (l < r) {
int mid = l + r >> 1;
if (get(mid, dist, hour) <= hour) r = mid;
else l = mid + 1;
}
return l;
}
};