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

题目地址(1883. 准时抵达会议现场的最小跳过休息次数)

https://leetcode-cn.com/problems/minimum-skips-to-arrive-at-meeting-on-time/

题目描述

给你一个整数 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] <= 105
1 <= speed <= 106
1 <= hoursBefore <= 107

前置知识

• 动态规划

• 浮点精度

公司

• 暂无

思路

刚看完题脑海中瞬间闪出了一个念头会不会是能力检测二分?

不熟悉能力检测二分的同学自己去翻我的二分专题

后面思考了一下发现不行。这是因为 possible(rest_count) 实现起来复杂度太高。这是因为 rest_count 分布情况是不确定的。令 dist 长度为 n，rest_count为 r，那么分布情况就有 $C_{n}^{r}$ 种。这种枚举显然是不合适的。

接下来，我想到使用动态规划。

令 dp[i][j] 表示到达 dist[i-1] 且休息 j 次（第 j 次休息完）所需要的时间，那么转移方程不难写：

• 如果第 j 次选择休息。那么 dp[i][j] = dp[i-1][j] + math.ceil(dist[i-1] / s)

• 如果第 j 次选择不休息。那么 dp[i][j] = dp[i-1][j-1] + cur

最后考虑边界。显然 i 和 j 都需要从 1 开始枚举，并且 j 不能大于 i。那么 i == 0 or j == 0 以及 i 和 j 全部为 0 的情况就需要特殊考虑。

在这里:

• j 从 0 枚举到 i

• dp[0][0] = 0 作为启动状态

• j == 0 不能选择不休息，因为这不符合题意

由于题目要求能准时到达的最少休息次数，因此从小到大枚举 j ，当 dp[n][j] <= hoursBefore 时，可以提前返回。

由于精度的原因，上面的代码可能有问题。

比如:

0.33333xxx33 + 0.33333xx33 + 0.3333xx33 = 1.0000000000xx002

这样当我们向上取整的时候本来可以准时到达的会被判断为不可准时到达。

解决的方法有很多。常见的有：

1. 化小数为整数

2. 取一个精度值，如果差值小于等于精度值，我们认为其相等。

这里我使用了第一种方法。感兴趣的可以自行研究一下其他方法。

这里我将 dp[i][j] 乘以 s，有效避免了精度问题。

需要注意的是 (cur + s - 1) // s 等价于 math.ceil(cur / s)，其中 s 为地板除， / 为实数除。

由于题目求最少，因此可以将 dp[i][j] 全部初始化为一个较大数，这里可以是 s * h + 1。

关键点

• 浮点精度

• dp[i][j] 定义为到达 dist[i-1] 且休息 j 次（第 j 次休息完）所需要的时间。

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def minSkips(self, dists: List[int], s: int, h: int) -> int:
        n = len(dists)
        dp = [[s * h + 1] * (n + 1) for i in range(n + 1)]
        dp[0][0] = 0
        for i in range(1, n + 1):
            cur = dists[i - 1]
            for j in range(i + 1):
                dp[i][j] = (dp[i - 1][j] + cur + s - 1) // s * s # rest
                if j > 0: dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + cur) # no rest
                if dp[-1][j] <= h * s:
                    return j
        return -1

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^2)$

• 空间复杂度：$O(n^2)$

此题解由 力扣刷题插件 自动生成。

力扣的小伙伴可以关注我，这样就会第一时间收到我的动态啦~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。