商标 做网站 是几类,关键词简谱,澄迈网站制作,如何制作一个简单的网页1.题目#xff1a;
给你一个数组 time #xff0c;其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。
每辆公交车可以 连续 完成多趟旅途#xff0c;也就是说#xff0c;一辆公交车当前旅途完成后#xff0c;可以 立马开始 下一趟旅途。每辆公交车 独立 …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 1051 time[i], totalTrips 107 2.思路步骤C语言版 初始化范围 设置 low 为 1因为时间不能为 0。设置 high 为 time[0] * totalTrips并通过遍历 time 数组获取所有公交车的最小值更新 high 为 min(time[i]) * totalTrips。 二分搜索 在 low 和 high 之间进行循环直到 low 不再小于 high。计算中间值 mid (low high) / 2。在这个步骤中直接计算在 mid 时间内所有公交车能完成的旅途数使用一个循环遍历 time 数组累加每辆车的旅途数trips mid / time[i]。如果旅途数大于或等于 totalTrips则说明在 mid 时间内可以完成足够的旅途因此更新 high mid否则更新 low mid 1。 返回结果 当结束循环时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; // 返回找到的最小时间
}
