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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数 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(int[] dist, int speed, int hoursBefore) {
        int n = dist.length;
        int[][] dp = new int[n][n];//dp[i][j]表示前i个skip j次最快完成的时间，由于都需要除以speed作为分母， 所以可以在最后才判断，这里直接记录分子即可
    
        dp[0][0] = dist[0]; 
        int distSum = dist[0];
        for (int i = 1; i < n; ++i) {
            //((speed - (dp[i - 1][0] % speed)) % speed)是为了取能整除speed的时间， 比如dp[i][0] = 9, speed = 4, 那么需要在12才能出发
            dp[i][0] = dp[i - 1][0] + ((speed - (dp[i - 1][0] % speed)) % speed) + dist[i];
            distSum += dist[i];
        }

        //如果所有跳过都无法在hoursBefore之前到达， 这里 加上 speed - 1是为了整除结果能向下取整得到正确判断
        //如果disSum = 20, speed = 4, hoursBefore = 5, 那么(20 + 4 - 1) / 4 <=  5  
        //如果disSum = 21, speed = 4, hoursBefore = 5, 那么(21 + 4 - 1) / 4 >  5 下同 
        if ((distSum + speed - 1) / speed > hoursBefore) {
            return -1;
        }
        //如果不需要跳过就能在hoursBefore之前到达
        if ((dp[n - 1][0] + speed - 1) / speed <= hoursBefore) {
            return 0;
        }
        
        for (int j = 1; j < n; j++) {
            dp[0][j] = dist[0];
            for (int i = 1; i < n; ++i) {
                //选择前面i - 1跳过j次，i - 1到 i不跳过 与 前面 i - 1跳过j-1次且i-1到i跳过 所花费的时间较小值
                dp[i][j] = Math.min(dp[i - 1][j] + ((speed - (dp[i - 1][j]  % speed)) % speed) + dist[i], dp[i - 1][j - 1] + dist[i]);
            }

            if ((dp[n - 1][j] + speed - 1) / speed <= hoursBefore) {
                return j;
            }
        }

        return -1;

    }

    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

# 总结

分析出几种情况，然后分别对各个情况实现

#Java