shelterofly

目标

给你一个数组 time ，其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。

每辆公交车可以 连续 完成多趟旅途，也就是说，一辆公交车当前旅途完成后，可以 立马开始 下一趟旅途。每辆公交车 独立 运行，也就是说可以同时有多辆公交车在运行且互不影响。

给你一个整数 totalTrips ，表示所有公交车 总共 需要完成的旅途数目。请你返回完成 至少 totalTrips 趟旅途需要花费的 最少 时间。

示例 1：

输入：time = [1,2,3], totalTrips = 5
输出：3
解释：
- 时刻 t = 1 ，每辆公交车完成的旅途数分别为 [1,0,0] 。
  已完成的总旅途数为 1 + 0 + 0 = 1 。
- 时刻 t = 2 ，每辆公交车完成的旅途数分别为 [2,1,0] 。
  已完成的总旅途数为 2 + 1 + 0 = 3 。
- 时刻 t = 3 ，每辆公交车完成的旅途数分别为 [3,1,1] 。
  已完成的总旅途数为 3 + 1 + 1 = 5 。
所以总共完成至少 5 趟旅途的最少时间为 3 。

示例 2：

输入：time = [2], totalTrips = 1
输出：2
解释：
只有一辆公交车，它将在时刻 t = 2 完成第一趟旅途。
所以完成 1 趟旅途的最少时间为 2 。

说明：

• 1 <= time.length <= 10^5
• 1 <= time[i], totalTrips <= 10^7

思路

一趟旅行可以选择 n 辆公交车，time[i] 表示第 i 辆公交完成旅途的时间，同一时间每辆公交车可以独立地运行，完成一趟旅途后立刻开始下一趟。问完成 totalTrips 次旅途最少需要花费多少时间。

使用二分法尝试最少花费的时间 least，完成旅途的次数为 sum(least/time[i])。查找的上界为 10^14（当只有一辆车，且它完成一趟旅行需要耗时 10^7，总共需要完成 10^7 趟旅行）。

可以优化的点是上下界的取值，我们可以求出公交车完成旅行所需时间的最大与最小值，假设所有公交完成时间均为最小值 min，那么平均每辆车需要完成 ⌈totalTrips / n⌉ 次旅途，时间的下界为⌈totalTrips / n⌉ * min，同理，上界为 ⌈totalTrips / n⌉ * max。

代码

/**
 * @date 2024-10-05 21:34
 */
public class MinimumTime2187 {

    public long minimumTime_v1(int[] time, int totalTrips) {
        int n = time.length;
        int max = 0;
        int min = Integer.MAX_VALUE;
        for (int i : time) {
            min = Math.min(i, min);
            max = Math.max(i, max);
        }
        long average = ((long) totalTrips - 1) / n + 1;
        long l = average * min;
        long r = average * max;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    public long minimumTime(int[] time, int totalTrips) {
        long l = 0L, r = 100000000000000L;
        long m = l + (r - l) / 2;
        while (l <= r) {
            if (check(time, totalTrips, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l;
    }

    private boolean check(int[] time, int totalTrips, long least) {
        long cnt = 0L;
        for (int i : time) {
            cnt += least / i;
            if (cnt >= totalTrips) {
                return true;
            }
        }
        return false;
    }
}

性能

优化上下界并没有明显的差距，并且还增加了编码的复杂度。

目标

给你一个浮点数 hour ，表示你到达办公室可用的总通勤时间。要到达办公室，你必须按给定次序乘坐 n 趟列车。另给你一个长度为 n 的整数数组 dist ，其中 dist[i] 表示第 i 趟列车的行驶距离（单位是千米）。

每趟列车均只能在整点发车，所以你可能需要在两趟列车之间等待一段时间。

• 例如，第 1 趟列车需要 1.5 小时，那你必须再等待 0.5 小时，搭乘在第 2 小时发车的第 2 趟列车。

返回能满足你准时到达办公室所要求全部列车的 最小正整数 时速（单位：千米每小时），如果无法准时到达，则返回 -1 。

生成的测试用例保证答案不超过 10^7 ，且 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.length
• 1 <= n <= 10^5
• 1 <= dist[i] <= 10^5
• 1 <= hour <= 10^9
• hours 中，小数点后最多存在两位数字

思路

从家到办公室需要依次乘坐 n 趟列车，列车只在整点发车，已知每趟车的行驶距离 dist[i]，问在给定通勤时间 hour 内到达办公室，列车的最低时速是多少，取正整数，如果无法按时到达返回 -1。

我们假设时速为 v，那么到达办公室的时间为 cost = Σ⌈dist[i]/v⌉ + dist[n-1]/v 前面 n - 1 趟车通勤时间需要考虑等车时间，所以要向上取整，最后一趟车则不需要向上取整。我们只需要满足cost <= hour 即可。由于时速需要取正整数，那么 v 也应该向上取整。

这道题的难点在于如何在 v 未知的情况下，向上取整后再求和，没办法直接计算。只能搜索解空间了，我们可以估算出 v 的取值范围，然后使用二分查找代入式子计算并与 hour 比较。v 的下界为 Σdist[i]/hour，上界是 max(dist[i]) * 100，这相当于是一趟车最大的距离除以最小的时间，如果这个速度还赶不上，那就赶不上了。

求和的时间复杂度为 O(n)，n 最大 10^5 ，距离最大 10^5 有可能溢出，应使用 long 类型。二分查找的复杂度为 O(nlogv)，v 最大值为 10^10， log2(10^10) ≈ 33.2，总的规模为 10 ^ 6 可行。

代码

/**
 * @date 2024-10-02 21:44
 */
public class MinSpeedOnTime1870 {

    public int minSpeedOnTime(int[] dist, double hour) {
        long sum = 0;
        for (int value : dist) {
            sum += value;
        }
        int v = (int) Math.ceil(sum / hour - 0.5);
        long l = v, r = 200 * sum, m = l + (r - l) / 2;
        while (l <= r) {
            if (check(dist, hour, m)) {
                r = m - 1;
            } else {
                l = m + 1;
            }
            m = l + (r - l) / 2;
        }
        return l > 200 * sum ? -1 : (int)l;
    }

    private boolean check(int[] dist, double hour, long m) {
        int n = dist.length;
        double cost = 0;
        for (int i = 0; i < n - 1; i++) {
            cost += Math.ceil((double) dist[i] / m);
        }
        cost += (double) dist[n - 1] / m;
        return cost <= hour;
    }

}

性能

目标

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式 ：

• 一张 为期一天 的通行证售价为 costs[0] 美元；
• 一张 为期七天 的通行证售价为 costs[1] 美元；
• 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回 你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费 。

示例 1：

输入：days = [1,4,6,7,8,20], costs = [2,7,15]
输出：11
解释： 
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划：
在第 1 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 1 天生效。
在第 3 天，你花了 costs[1] = $7 买了一张为期 7 天的通行证，它将在第 3, 4, ..., 9 天生效。
在第 20 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 20 天生效。
你总共花了 $11，并完成了你计划的每一天旅行。

示例 2：

输入：days = [1,2,3,4,5,6,7,8,9,10,30,31], costs = [2,7,15]
输出：17
解释：
例如，这里有一种购买通行证的方法，可以让你完成你的旅行计划： 
在第 1 天，你花了 costs[2] = $15 买了一张为期 30 天的通行证，它将在第 1, 2, ..., 30 天生效。
在第 31 天，你花了 costs[0] = $2 买了一张为期 1 天的通行证，它将在第 31 天生效。 
你总共花了 $17，并完成了你计划的每一天旅行。

说明：

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days 按顺序严格递增
• costs.length == 3
• 1 <= costs[i] <= 1000

思路

有一个严格递增的出行计划表 days，days[i] 表示计划在这一天出行。出行需要持有通行证，通行证有三种，1 天有效期，7 天有效期，30 天有效期，价格各不相同。求完成出行计划所需的最低花费。

定义 dp[i] 表示截止到第 i 天的最小花费，初始化数组大小为 days[n - 1] + 1。

• 如果第 i 天需要出行，dp[i] = Math.min(dp[i - 1] + cost[0], dp[i - 7] + cost[1], dp[i - 30] + cost[2])
• 否则，dp[i] = dp[i - 1]

网友最快题解定义 dp[i] 为旅行了 i 天的最小花费，这样与 days[i] 的数据范围无关，仅与出行天数 days.length 有关。

代码

/**
 * @date 2024-10-01 20:43
 */
public class MincostTickets983 {

    /**
     * 针对 前面方法 的优化
     * 去掉初始化 dp[i] 为截止到第i天 使用一天票的总花费，
     * 使用数组记录是否出行
     */
    public int mincostTickets_v1(int[] days, int[] costs) {
        int n = days.length;
        int end = days[n - 1];
        int[] dp = new int[end + 1];
        boolean[] isTravel = new boolean[end + 1];
        for (int day : days) {
            isTravel[day] = true;
        }
        for (int i = 1; i <= end; i++) {
            int tmp7 = Math.max(0, i - 7);
            int tmp30 = Math.max(0, i - 30);
            if (isTravel[i]) {
                dp[i] = Math.min(dp[i - 1] + costs[0], dp[tmp7] + costs[1]);
                dp[i] = Math.min(dp[i], dp[tmp30] + costs[2]);
            } else {
                dp[i] = dp[i - 1];
            }
        }
        return dp[end];
    }

    public int mincostTickets(int[] days, int[] costs) {
        int n = days.length;
        int end = days[n - 1];
        int[] dp = new int[end + 1];
        int last = 0;
        int index = 0;
        Set<Integer> set = new HashSet<>(n);
        for (int day : days) {
            set.add(day);
            while (index < day) {
                dp[index++] = last;
            }
            dp[day] += last + costs[0];
            last = dp[day];
        }
        for (int i = 1; i <= end; i++) {
            int tmp7 = Math.max(0, i - 7);
            int tmp30 = Math.max(0, i - 30);
            if (!set.contains(i)) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = Math.min(dp[i - 1] + costs[0], dp[tmp7] + costs[1]);
                dp[i] = Math.min(dp[i], dp[tmp30] + costs[2]);
            }
        }
        return dp[end];
    }

}

性能

• 去掉 dp[i] 的初始化，刚开始写的是将其初始化为截止到第 i 天使用一天票的总花费
• 使用数组记录是否出行