class Solution {
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
}
};
1870. 准时到达的列车最小时速
给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。
每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。
1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。
生成的测试用例保证答案不超过 107 ，且 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.length1 <= n <= 1051 <= dist[i] <= 1051 <= hour <= 109hours 中，小数点后最多存在两位数字原站题解
rust 解法, 执行用时: 22 ms, 内存消耗: 3.4 MB, 提交时间: 2024-10-02 22:54:38
impl Solution {
pub fn min_speed_on_time(dist: Vec<i32>, hour: f64) -> i32 {
let n = dist.len();
let h100 = (hour * 100.0).round() as i64; // 下面不会用到任何浮点数
let delta = h100 - (n as i64 - 1) * 100;
if delta <= 0 { // 无法到达终点
return -1;
}
let max_dist = *dist.iter().max().unwrap();
if h100 <= n as i64 * 100 { // 特判
// 见题解中的公式
return max_dist.max(((dist[n - 1] * 100 - 1) as i64 / delta) as i32 + 1);
}
let check = |v: i32| -> bool {
let mut t = 0i64;
for &d in &dist[..n - 1] {
t += ((d - 1) / v + 1) as i64;
}
(t * v as i64 + dist[n - 1] as i64) * 100 <= h100 * v as i64
};
let mut left = 0;
let h = (h100 / (n * 100) as i64) as i32;
let mut right = (max_dist - 1) / h + 1;
while left + 1 < right {
let mid = (left + right) / 2;
if check(mid) {
right = mid;
} else {
left = mid;
}
}
right
}
}
javascript 解法, 执行用时: 107 ms, 内存消耗: 61.7 MB, 提交时间: 2024-10-02 22:54:16
/**
* @param {number[]} dist
* @param {number} hour
* @return {number}
*/
var minSpeedOnTime = function(dist, hour) {
const n = dist.length;
const h100 = Math.round(hour * 100);
const delta = h100 - (n - 1) * 100;
if (delta <= 0) { // 无法到达终点
return -1;
}
const maxDist = Math.max(...dist);
if (h100 <= n * 100) { // 特判
// 见题解中的公式
return Math.max(maxDist, Math.ceil(dist[n - 1] * 100 / delta));
}
function check(v) {
let t = 0;
for (let i = 0; i < n - 1; i++) {
t += Math.ceil(dist[i] / v);
}
return (t * v + dist[n - 1]) * 100 <= h100 * v;
}
const h = Math.floor(h100 / (n * 100));
let left = 0, right = Math.ceil(maxDist / h);
while (left + 1 < right) {
const mid = Math.floor((left + right) / 2);
if (check(mid)) {
right = mid;
} else {
left = mid;
}
}
return right;
};
python3 解法, 执行用时: 285 ms, 内存消耗: 27.6 MB, 提交时间: 2024-10-02 22:53:58
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
n = len(dist)
h100 = round(hour * 100) # 下面不会用到任何浮点数
delta = h100 - (n - 1) * 100
if delta <= 0: # 无法到达终点
return -1
max_dist = max(dist)
if h100 <= n * 100: # 特判
# 见题解中的公式
return max(max_dist, (dist[-1] * 100 - 1) // delta + 1)
def check(v: int) -> bool:
t = n - 1 # n-1 个上取整中的 +1 先提出来
for d in dist[:-1]:
t += (d - 1) // v
return (t * v + dist[-1]) * 100 <= h100 * v
h = h100 // (n * 100)
return bisect_left(range((max_dist - 1) // h + 1), True, 1, key=check)
cpp 解法, 执行用时: 228 ms, 内存消耗: 99.4 MB, 提交时间: 2023-09-26 17:55:17
class Solution {
public:
int minSpeedOnTime(vector<int>& dist, double hour) {
int n = dist.size();
// 将 hour 乘 100 以转为整数
long long hr = llround(hour * 100);
// 时间必须要大于路程段数减 1
if (hr <= (n - 1) * 100){
return -1;
}
// 二分
int l = 1;
int r = 1e7;
while (l < r){
int mid = l + (r - l) / 2;
// 判断当前时速是否满足时限
long long t = 0;
// 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)
for (int i = 0; i < n - 1; ++i){
t += (dist[i] - 1) / mid + 1;
}
// 最后一段贡献的时间： dist[n-1] / mid
t *= mid;
t += dist[n-1];
if (t * 100 <= hr * mid){ // 通分以转化为整数比较
r = mid;
}
else{
l = mid + 1;
}
}
return l; // 满足条件的最小时速
}
};
python3 解法, 执行用时: 1812 ms, 内存消耗: 27.4 MB, 提交时间: 2023-09-26 17:55:00
class Solution:
def minSpeedOnTime(self, dist: List[int], hour: float) -> int:
n = len(dist)
hr = round(hour * 100)
# 时间必须要大于路程段数减 1
if hr <= 100 * (n - 1):
return -1
# 判断当前时速是否满足时限
def check(speed: int) -> bool:
t = 0
# 前 n-1 段中第 i 段贡献的时间： floor(dist[i] / mid)
for i in range(n - 1):
t += (dist[i] - 1) // speed + 1
# 最后一段贡献的时间： dist[n-1] / mid
t *= speed
t += dist[-1]
return t * 100 <= hr * speed # 通分以转化为整数比较
# 二分
l, r = 1, 10 ** 7
while l < r:
mid = l + (r - l) // 2
if check(mid):
r = mid
else:
l = mid + 1
return l # 满足条件的最小时速
java 解法, 执行用时: 65 ms, 内存消耗: 57.2 MB, 提交时间: 2023-09-26 17:53:38
/**
* 首先判断特殊情况：当所需时间向上取整后仍然小于 dist 长度，那么注定到不了，
* 就直接返回 false。 然后进行二分搜索，范围是 [1, Integer.MAX_VALUE]。
*/
class Solution {
public int minSpeedOnTime(int[] dist, double hour) {
if (dist.length > Math.ceil(hour)) return -1;
// 搜索边界
int left = 1, right = Integer.MAX_VALUE;
while (left < right) {
int mid = left + (right - left) / 2;
// 如果以 mid 速度可达，那么就尝试减小速度
if (check(dist, hour, mid)) right = mid;
// 否则就需要加了
else left = mid + 1;
}
return left;
}
private boolean check(int[] dist, double hour, int speed) {
double cnt = 0.0;
// 对除了最后一个站点以外的时间进行向上取整累加
for (int i = 0; i < dist.length - 1; ++i) {
// 除法的向上取整
cnt += (dist[i] + speed - 1) / speed;
}
// 加上最后一个站点所需的时间
cnt += (double) dist[dist.length - 1] / speed;
return cnt <= hour;
}
}
golang 解法, 执行用时: 256 ms, 内存消耗: 8.1 MB, 提交时间: 2023-09-26 17:51:01
/**
* 首先，由于除了最后一趟列车，前面的每趟列车至少花费 1 小时，
* 且最后一趟列车花费的时间大于 0，因此 hour 必须严格大于 n−1。
*/
func minSpeedOnTime(dist []int, hour float64) int {
h100 := int(math.Round(hour * 100))
n := len(dist)
if h100 <= (n-1)*100 { // hour 必须严格大于 n-1
return -1
}
return 1 + sort.Search(1e7-1, func(v int) bool {
v++
h := n - 1
for _, d := range dist[:n-1] {
h += (d - 1) / v
}
return (h*v+dist[n-1])*100 <= h100*v
})
}