准时抵达会议现场的最小跳过休息次数

1883. 准时抵达会议现场的最小跳过休息次数

给你一个整数 hoursBefore ，表示你要前往会议所剩下的可用小时数。要想成功抵达会议现场，你必须途经 n 条道路。道路的长度用一个长度为 n 的整数数组 dist 表示，其中 dist[i] 表示第 i 条道路的长度（单位：千米）。另给你一个整数 speed ，表示你在道路上前进的速度（单位：千米每小时）。

当你通过第 i 条路之后，就必须休息并等待，直到 下一个整数小时 才能开始继续通过下一条道路。注意：你不需要在通过最后一条道路后休息，因为那时你已经抵达会议现场。

例如，如果你通过一条道路用去 1.4 小时，那你必须停下来等待，到 2 小时才可以继续通过下一条道路。如果通过一条道路恰好用去 2 小时，就无需等待，可以直接继续。

然而，为了能准时到达，你可以选择跳过一些路的休息时间，这意味着你不必等待下一个整数小时。注意，这意味着与不跳过任何休息时间相比，你可能在不同时刻到达接下来的道路。

例如，假设通过第 1 条道路用去 1.4 小时，且通过第 2 条道路用去 0.6 小时。跳过第 1 条道路的休息时间意味着你将会在恰好 2 小时完成通过第 2 条道路，且你能够立即开始通过第 3 条道路。

返回准时抵达会议现场所需要的 最小跳过次数 ，如果 无法准时参会 ，返回 -1 。

示例 1：

输入：dist = [1,3,2], speed = 4, hoursBefore = 2
输出：1
解释：
不跳过任何休息时间，你将用 (1/4 + 3/4) + (3/4 + 1/4) + (2/4) = 2.5 小时才能抵达会议现场。
可以跳过第 1 次休息时间，共用 ((1/4 + 0) + (3/4 + 0)) + (2/4) = 1.5 小时抵达会议现场。
注意，第 2 次休息时间缩短为 0 ，由于跳过第 1 次休息时间，你是在整数小时处完成通过第 2 条道路。

示例 2：

输入：dist = [7,3,5,5], speed = 2, hoursBefore = 10
输出：2
解释：
不跳过任何休息时间，你将用 (7/2 + 1/2) + (3/2 + 1/2) + (5/2 + 1/2) + (5/2) = 11.5 小时才能抵达会议现场。
可以跳过第 1 次和第 3 次休息时间，共用 ((7/2 + 0) + (3/2 + 0)) + ((5/2 + 0) + (5/2)) = 10 小时抵达会议现场。

示例 3：

输入：dist = [7,3,5,5], speed = 1, hoursBefore = 10
输出：-1
解释：即使跳过所有的休息时间，也无法准时参加会议。

提示：

n == dist.length
1 <= n <= 1000
1 <= dist[i] <= 10⁵
1 <= speed <= 10⁶
1 <= hoursBefore <= 10⁷

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int minSkips(vector<int>& dist, int speed, int hoursBefore) { } };

rust 解法, 执行用时: 23 ms, 内存消耗: 10.2 MB, 提交时间: 2024-04-19 09:05:51

use std::f64::INFINITY;

impl Solution {
    pub fn min_skips(dist: Vec<i32>, speed: i32, hours_before: i32) -> i32 {
        // 可忽略误差
        let eps = 1e-7;
        let n = dist.len();
        let mut f = vec![vec![f64::INFINITY; n + 1]; n + 1];
        f[0][0] = 0.0;
        for i in 1..= n {
            for j in 0..= i {
                if j != i {
                    f[i][j] = f[i][j].min((f[i - 1][j] + (dist[i - 1] as f64) / (speed as f64) - eps).ceil());
                }
                if j != 0 {
                    f[i][j] = f[i][j].min(f[i - 1][j - 1] + (dist[i - 1] as f64) / (speed as f64));
                }
            }
        }

        for j in 0..= n {
            if f[n][j] < (hours_before as f64) + eps {
                return j as i32;
            }
        }
        -1
    }
}

javascript 解法, 执行用时: 174 ms, 内存消耗: 79.9 MB, 提交时间: 2024-04-19 09:05:37

/**
 * @param {number[]} dist
 * @param {number} speed
 * @param {number} hoursBefore
 * @return {number}
 */
var minSkips = function(dist, speed, hoursBefore) {
    // 可忽略误差
    const EPS = 1e-7;
    const n = dist.length;
    const f = new Array(n + 1).fill(0).map(() => new Array(n + 1).fill(Infinity));
    f[0][0] = 0;
    for (let i = 1; i <= n; i++) {
        for (let j = 0; j <= i; j++) {
            if (j !== i) {
                f[i][j] = Math.min(f[i][j], Math.ceil(f[i - 1][j] + dist[i - 1] / speed - EPS));
            }
            if (j !== 0) {
                f[i][j] = Math.min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed);
            }
        }
    }

    for (let j = 0; j <= n; j++) {
        if (f[n][j] < hoursBefore + EPS) {
            return j;
        }
    }
    return -1;
};

python3 解法, 执行用时: 3116 ms, 内存消耗: 39.2 MB, 提交时间: 2023-10-25 23:17:33

class Solution:
    def minSkips(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        # 可忽略误差
        EPS = 1e-7
        
        n = len(dist)
        f = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0.
        for i in range(1, n + 1):
            for j in range(i + 1):
                if j != i:
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + dist[i - 1] / speed - EPS))
                if j != 0:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1] / speed)
        
        for j in range(n + 1):
            if f[n][j] < hoursBefore + EPS:
                return j
        return -1
        

    def minSkips2(self, dist: List[int], speed: int, hoursBefore: int) -> int:
        n = len(dist)
        f = [[float("inf")] * (n + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(i + 1):
                if j != i:
                    f[i][j] = min(f[i][j], ((f[i - 1][j] + dist[i - 1] - 1) // speed + 1) * speed)
                if j != 0:
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1])
        
        for j in range(n + 1):
            if f[n][j] <= hoursBefore * speed:
                return j
        return -1

cpp 解法, 执行用时: 216 ms, 内存消耗: 125.9 MB, 提交时间: 2023-10-25 23:17:04

class Solution {
private:
    // 可忽略误差
    static constexpr double EPS = 1e-7;
    // 极大值
    static constexpr double INFTY = 1e20;

public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<vector<double>> f(n + 1, vector<double>(n + 1, INFTY));
        f[0][0] = 0.;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j != i) {
                    f[i][j] = min(f[i][j], ceil(f[i - 1][j] + (double)dist[i - 1] / speed - EPS));
                }
                if (j != 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + (double)dist[i - 1] / speed);
                }
            }
        }
        for (int j = 0; j <= n; ++j) {
            if (f[n][j] < hoursBefore + EPS) {
                return j;
            }
        }
        return -1;
    }
};

cpp 解法, 执行用时: 200 ms, 内存消耗: 125.8 MB, 提交时间: 2023-10-25 23:16:47

class Solution {
private:
    using LL = long long;

public:
    int minSkips(vector<int>& dist, int speed, int hoursBefore) {
        int n = dist.size();
        vector<vector<LL>> f(n + 1, vector<LL>(n + 1, LLONG_MAX / 2));
        f[0][0] = 0;
        for (int i = 1; i <= n; ++i) {
            for (int j = 0; j <= i; ++j) {
                if (j != i) {
                    f[i][j] = min(f[i][j], ((f[i - 1][j] + dist[i - 1] - 1) / speed + 1) * speed);
                }
                if (j != 0) {
                    f[i][j] = min(f[i][j], f[i - 1][j - 1] + dist[i - 1]);
                }
            }
        }
        for (int j = 0; j <= n; ++j) {
            if (f[n][j] <= (LL)hoursBefore * speed) {
                return j;
            }
        }
        return -1;
    }
};

golang 解法, 执行用时: 40 ms, 内存消耗: 2.7 MB, 提交时间: 2023-10-25 23:16:31

func minSkips(dist []int, speed, hoursBefore int) (ans int) {
	n := len(dist)
	ceilDist := func(d int) int { return (d + speed - 1) / speed * speed }
	f := make([]int, n)
	for i := range f {
		f[i] = 2e9
	}
	f[0] = 0
	for _, d := range dist {
		for j := n - 1; j > 0; j-- {
			f[j] = min(ceilDist(f[j]+d), f[j-1]+d)
		}
		f[0] += ceilDist(d)
	}
	for i, d := range f { // 从小到大遍历跳过次数
		if (d+speed-1)/speed <= hoursBefore { 
			return i // 返回第一个满足时间要求的
		}
	}
	return -1
}

func min(a, b int) int { if a < b { return a }; return b }

上一题

下一题

详情