C语言入门基础题（力扣）：完成旅途的最少时间（C语言版）

时间：2024-10-09 19:09:18

1.题目：

给你一个数组 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 <= 105
  • 1 <= time[i], totalTrips <= 107

2.思路步骤（C语言版）

  1. 初始化范围：

    • 设置 low 为 1，因为时间不能为 0。
    • 设置 high 为 time[0] * totalTrips，并通过遍历 time 数组获取所有公交车的最小值，更新 high 为 min(time[i]) * totalTrips。

  2. 二分搜索：

    • 在 low 和 high 之间进行循环，直到 low 不再小于 high。
    • 计算中间值 mid = (low + high) / 2。
    • 在这个步骤中，直接计算在 mid 时间内所有公交车能完成的旅途数，使用一个循环遍历 time 数组累加每辆车的旅途数：trips += mid / time[i]。
    • 如果旅途数大于或等于 totalTrips，则说明在 mid 时间内可以完成足够的旅途，因此更新 high = mid；否则更新 low = mid + 1。

  3. 返回结果：

    • 当结束循环时，low 即为至少完成 totalTrips 趟旅途所需的最少时间。

3.代码：

long long minimumTime(int* time, int timeSize, int totalTrips) {
    long long low = 1;
    
    long long high = (long long)time[0] * totalTrips; // 初始化高值

    for (int i = 1; i < timeSize; i++) {
        if ((long long)time[i] * totalTrips < high) {
            high = (long long)time[i] * totalTrips; // 更新高值
        }
    }

    while (low < high) {
        long long mid = (low + high) / 2;

        long long trips = 0;
        for (int i = 0; i < timeSize; i++) {
            trips += mid / time[i];
        }
        if (trips >= totalTrips) {
            high = mid; // 可以完成足够旅途，尝试更短的时间
        } else {
            low = mid + 1; // 不够，需要更长的时间
        }
    }

    return low; // 返回找到的最小时间
}

相关文章