公司手机网站制作廊坊网站群建设

公司手机网站制作,廊坊网站群建设,管理系统网站开发报价,网站建设续费是那些题目描述给你一个数组 time #xff0c;其中 time[i] 表示第 i 辆公交车完成 一趟旅途 所需要花费的时间。每辆公交车可以 连续 完成多趟旅途#xff0c;也就是说#xff0c;一辆公交车当前旅途完成后#xff0c;可以 立马开始 下一趟旅途。每辆公交车 独立 运行#xff0…题目描述给你一个数组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解决方案算法目标给定多辆车的单趟完成时间和需要完成的总趟数找出完成所有趟数所需的最少时间。核心思路确定时间范围时间在[0, 最慢车×总趟数]之间二分查找时间尝试不同的时间计算在该时间内能完成多少趟寻找最小值找到能满足总趟数要求的最小时间算法步骤1. 确定查找范围int min_tmp *min_element(time.begin(), time.end()); long long left -1; // 不可行的下界 long long right (long long)min_tmp * totalTrips; // 可行的上界下界-1肯定不够的时间上界用最慢的车完成所有趟数的时间使用开区间(left, right)left永远不可行right永远可行2. 二分查找主循环while(left 1 right) { long long mid left (right - left) / 2; // 尝试的时间 // 计算在时间mid内能完成的趟数 // 判断并更新边界 }3. 计算可完成趟数long long tmp 0; for(auto p : time) { tmp mid / p; // 每辆车在时间mid内能完成的趟数 if(tmp totalTrips) break; // 提前退出优化 }对每辆车在时间mid内能完成mid / time[i]趟累加所有车的趟数提前退出当已满足总趟数要求时停止计算4. 判断并更新边界if(tmp totalTrips) {left mid; // 时间不够需要更多时间} else {right mid; // 时间足够尝试更少时间}5. 返回结果return right; // 最小的可行时间关键点二分查找对象总时间t不是车辆数验证条件在时间t内能完成的趟数≥ totalTrips搜索方向寻找满足条件的最小t整数除法mid / p自动向下取整因为一趟必须完整完成时间复杂度寻找最慢车O(n)二分查找O(log(min_time × totalTrips))每次验证O(n)总时间O(n log T)示例time [1, 2, 3] totalTrips 5 查找过程 1. 范围: t ∈ [0, 1×55] 2. 尝试 t2: 可完成3趟 5 → 不够 3. 尝试 t3: 可完成5趟 ≥ 5 → 足够 4. 最终结果: t3算法正确性单调性时间越长能完成的趟数越多边界保证left永远不可行right永远可行最终right是最小的可行时间优化亮点提前退出当趟数已达标时立即停止计算开区间二分避免边界处理复杂类型安全使用long long防止溢出函数源码class Solution { public: long long minimumTime(vectorint time, int totalTrips) { int min_tmptime[0]; for(auto p:time){ min_tmpmin(p,min_tmp); } long long left-1; long long right(long long)min_tmp*totalTrips; while(left1right){ long long mid(leftright)/2; long long tmp0; for(auto p:time){ tmpmid/p; if(tmp totalTrips) break; // 提前退出优化 } if(tmptotalTrips) leftmid; else rightmid; } return right; } };