目标
给你一个数组 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;
}
}
性能
优化上下界并没有明显的差距，并且还增加了编码的复杂度。
