科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以仓库 leetcode/weekly/282/c/c.md 为主体完整讲解 LeetCode 第 282 场周赛第三题「完成旅途的最少时间」Minimum Time to Complete Trips的二分答案解法从单调性分析、二分上界选取、判定函数设计到 Go 与 Python 3.10 的两份可运行实现并结合 leetcode/weekly/282/c/c.go、leetcode/weekly/282/c/c_test.go 与 copypasta/sort.go 中的sort.Search使用技巧做源码级验证。读完你既能独立复现此题也能把「二分答案求最小可行值」这套模板迁移到其他最小化最大值/最大化最小值类问题上。题目背景与问题抽象题目给定n辆公交车其中time[i]表示第i辆车完成一趟旅途所需的时间单位不限下文统一为单位时间。所有车辆同时开始运行问完成totalTrips趟旅途所需的最少时间是多少。核心约束有两个一辆车跑完一趟后可以立刻开始下一趟因此车辆 $i$ 在 $x$ 时间内最多能完成 $\lfloor x / time[i] \rfloor$ 趟车辆之间互不干扰总完成量是各车完成量之和。问题本质给定时间上限 $x$求一个最小化的 $x$使得所有车在该时间内完成的旅途总数达到totalTrips。核心思路为什么可以二分答案单调性分析二分的合法性来源定义判定函数$$ f(x)\sum_{i0}^{n-1}\Big\lfloor\dfrac{x}{\textit{time}[i]}\Big\rfloor $$即 $x$ 时间内所有车合计能完成的旅途趟数。显然 $f(x)$ 关于 $x$单调不减时间越多能完成的旅途只会越多或持平。于是是否存在 $x$ 使得 $f(x)\ge \textit{totalTrips}$这一谓词在 $x$ 从小到大时呈现先 false、后 true的形态这正是标准二分的前提条件。二分上界的选取文档原话原文档给出了上界的直觉答案不可能超过让最慢的车跑totalTrips趟所花费的时间即$$ \text{upper} \textit{totalTrips} \times \max(\textit{time}) $$在这个时间内仅凭最慢的车一辆就能独自完成totalTrips趟其余车辆只会贡献更多因此上界一定可行。这也是 Python 实现中totalTrips * max(time)的来源。判定函数二分答案 $x$ 时计算 $f(x)$ 并与totalTrips比较若 $f(x) \ge \textit{totalTrips}$说明 $x$ 可行或已经偏大向左收缩上界否则 $x$ 不可行向右扩大下界。最终二分停下的位置就是第一个使判定为 true 的 $x$即最小可行时间也就是答案。参考实现一Go 版本仓库实际代码仓库中的实现位于 leetcode/weekly/282/c/c.go使用了标准库sort.Searchpackage main import sort // github.com/EndlessCheng/codeforces-go func minimumTime(time []int, totalTrips int) int64 { min : time[0] for _, v : range time[1:] { if v min { min v } } return int64(sort.Search(totalTrips*min, func(maxTime int) bool { tot : 0 for _, t : range time { tot maxTime / t if tot totalTrips { return true } } return false })) }需要理解sort.Search(n, f)的语义在 $[0, n)$ 内返回第一个使f(x)为 true 的 $x$要求f满足先 false 后 true。这里f(x)正是$x$ 时间内能完成至少totalTrips趟因此第一个 true 的位置即为最小可行时间无需在二分结束后再做任何修正。f(0)0totalTrips天然为 false不会干扰结果。文档原版 Go 代码使用的是更保守的上界totalTrips*1e7题目数据范围内 $\max(\textit{time})\le 10^7$ 时与totalTrips*max(time)等价直接写死可省去求 max 的循环仓库版本则进一步做了上界优化见下文。参考实现二Python 3.10 版本带 key 的一行二分原文档特别指出Python 3.10 新增带key参数的bisect_left可以把序列元素 - 判定值的映射内联进二分从而一行解决此题class Solution: def minimumTime(self, time: List[int], totalTrips: int) - int: return bisect_left(range(totalTrips * max(time)), totalTrips, keylambda x: sum(x // t for t in time))这里的技巧值得拆解range(totalTrips * max(time))是一个惰性的整数序列下标 $x$ 即时间keylambda x: sum(x // t for t in time)把下标映射成 $f(x)$bisect_left在伪序列 $f(0),f(1),\dots$上查找第一个 $\ge \textit{totalTrips}$ 的位置返回的下标就是答案。由于range是惰性求值key函数只在二分访问到的位置被调用时间/空间复杂度与手写二分完全一致是 Python 3.10 环境下的极简写法。细节与优化更紧的上界与提前退出用min(time)替换max(time)缩小二分区间一个值得注意的优化是仓库代码用totalTrips*min而不是totalTrips*max作为二分上界。理由同样成立让最快的车跑totalTrips趟所需时间为 $\textit{totalTrips}\times\min(\textit{time})$在这个时间内最快的一辆车就能独自完成totalTrips趟因此全局完成量 $\ge \textit{totalTrips}$上界可行。由于 $\min \le \max$用 min 得到的二分区间更窄二分次数更少而正确性不变。这是一个通用的二分答案优化上界只需可行不必最松选择更紧的可行上界能直接减少常数。仓库实现以一次 O(n) 的求 min 循环换取对数级区间缩小实测收益明显。判定函数内的提前退出注意c.go判定函数中这一行if tot totalTrips { return true }每累加一辆车的贡献后立刻与totalTrips比较一旦达标就提前返回避免继续遍历剩余车辆。这是典型的可行性判定短路优化在答案附近的大多数二分轮次中车辆数n可能很大短路能显著减少判定函数的平均开销。从仓库模板库 copypasta/sort.go 的二分答案题单可以看到这种判定函数内提前返回的写法是仓库中二分答案类题目的一贯风格。整数范围注意totalTrips * min(time)以及x/t的累加都可能超过 32 位整数范围。原题中time[i]与totalTrips均可达到 $10^7$ 量级乘积接近 $10^{14}$因此 Go 实现返回类型为int64判定的中间变量tot也应在语言默认整数宽度不足以容纳时使用 64 位类型仓库当前写法依赖 Go 在 64 位平台上int即 64 位跨平台提交时需留意。复杂度分析二分区间长度 $U\textit{totalTrips}\times\min(\textit{time})$sort.Search的二分次数约为 $O(\log U)$更精确地说等于 $U$ 的二进制位数bits.Len(U)见 copypasta/sort.go 的说明每次判定需遍历 $n$ 辆车最坏 $O(n)$配合短路平均更优总时间复杂度 $O(n\log(\textit{totalTrips}\cdot\min(\textit{time})))$空间复杂度 $O(1)$仅常数个临时变量。仓库测试验证leetcode/weekly/282/c/c_test.go 通过仓库自带的testutil.RunLeetCodeFuncWithExamples驱动两个官方示例输入输出验证要点time[1,2,3],totalTrips53时间 3 内车 1 跑 3 趟、车 2 跑 1 趟、车 3 跑 1 趟合计 5 趟刚好达标时间 2 内合计 $\lfloor 2/1\rfloor\lfloor 2/2\rfloor\lfloor 2/3\rfloor35$故答案确为 3time[2],totalTrips12单辆车每趟 2 单位时间跑 1 趟至少需要 2测试框架leetcode/testutil/leetcode.go负责把[][]string形式的原始用例解析为函数入参并比对输出用例数据以纯文本内嵌在测试文件中targetCaseNum : 0表示运行全部示例。你可以直接在仓库leetcode/weekly/282/c/目录下执行go test复现验证。延伸sort.Search二分答案的通用模板仓库视角本题是二分答案求最小可行值的教科书案例仓库在 copypasta/sort.go 中沉淀了配套模板与技巧值得一并掌握先 false 后 true 的要求sort.Search(n, f)要求f随下标单调翻转。本题判定$f(x)\ge totalTrips$恰好先 false 后 true直接可用。求最大值时的翻转技巧其一若目标是最大的使某条件成立的 $x$条件先 true 后 false可以对!f(x)做二分再减一或在f内部将x后判断取反条件从而复用sort.Search的单调假设。具体示例二分求int(sqrt(90))见 copypasta/sort.go。二分区间平移searchRange当答案不在 $[0,n)$ 而在 $[l,r)$ 时写l sort.Search(r-l, func(x int) bool { x l; ... })模板见 copypasta/sort.go。分类题单copypasta/sort.go 给出了二分答案的完整题型地图二分答案求最小 / 求最大 / 二分间接值 / 最小化最大值 / 最大化最小值 / 隐藏的二分并附有大量 Codeforces、AtCoder 等平台的练习题目编号可作为该技巧的进阶训练清单。小结「完成旅途的最少时间」的完整解题链条是抽象出单调的判定函数 - 选取一个一定可行的上界 - 二分第一个可行点。文档给出了最直观的totalTrips * max(time)上界与 Python 3.10 带key的一行二分仓库实现则在保持同一算法框架的前提下用totalTrips * min(time)收紧上界、并在判定内做提前退出配合sort.Search得到简洁且常数更优的 Go 解法。遇到求最小可行 X类问题最小化最大值、最大化最小值、第 K 小等都可以直接套用这套模板。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐在网格图中访问格子的最少时间Dijkstra 与二分答案 BFS 双解法剖析 —— codeforces-go 第 334 场周赛 D 题题解精读在网格图中访问格子的最少时间Dijkstra 与二分答案 BFS 双解法剖析 —— codeforces go 第 334 场周赛 D 题题解精读 本篇文科学计算最小化最大等待时间的多维 DP 与二分答案解法力扣双周赛 188 第 4 题源码级详解codeforces-go最小化最大等待时间的多维 DP 与二分答案解法力扣双周赛 188 第 4 题源码级详解codeforces go 导读本文系统讲解力扣双周赛 188 第科学计算codeforces-go 题解精讲LeetCode 周赛 326 D 题「区间内最近的质数」的筛法与二分实现codeforces go 题解精讲LeetCode 周赛 326 D 题「区间内最近的质数」的筛法与二分实现 本篇技术指南以算法竞赛模板库 codeforc科学计算上一篇推荐开源项目Immutables - Java中不可变对象的优雅解决方案下一篇CairoShell 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/10/10 1:19:39 · 阅读 1.2k codeforces-go 题解：第 282 场周赛「完成旅途的最少时间」二分答案精讲（含 sort.Search 模板与上界优化）
科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以仓库 leetcode/weekly/282/c/c.md 为主体完整讲解 LeetCode 第 282 场周赛第三题「完成旅途的最少时间」Minimum Time to Complete Trips的二分答案解法从单调性分析、二分上界选取、判定函数设计到 Go 与 Python 3.10 的两份可运行实现并结合 leetcode/weekly/282/c/c.go、leetcode/weekly/282/c/c_test.go 与 copypasta/sort.go 中的sort.Search使用技巧做源码级验证。读完你既能独立复现此题也能把「二分答案求最小可行值」这套模板迁移到其他最小化最大值/最大化最小值类问题上。题目背景与问题抽象题目给定n辆公交车其中time[i]表示第i辆车完成一趟旅途所需的时间单位不限下文统一为单位时间。所有车辆同时开始运行问完成totalTrips趟旅途所需的最少时间是多少。核心约束有两个一辆车跑完一趟后可以立刻开始下一趟因此车辆 $i$ 在 $x$ 时间内最多能完成 $\lfloor x / time[i] \rfloor$ 趟车辆之间互不干扰总完成量是各车完成量之和。问题本质给定时间上限 $x$求一个最小化的 $x$使得所有车在该时间内完成的旅途总数达到totalTrips。核心思路为什么可以二分答案单调性分析二分的合法性来源定义判定函数$$ f(x)\sum_{i0}^{n-1}\Big\lfloor\dfrac{x}{\textit{time}[i]}\Big\rfloor $$即 $x$ 时间内所有车合计能完成的旅途趟数。显然 $f(x)$ 关于 $x$单调不减时间越多能完成的旅途只会越多或持平。于是是否存在 $x$ 使得 $f(x)\ge \textit{totalTrips}$这一谓词在 $x$ 从小到大时呈现先 false、后 true的形态这正是标准二分的前提条件。二分上界的选取文档原话原文档给出了上界的直觉答案不可能超过让最慢的车跑totalTrips趟所花费的时间即$$ \text{upper} \textit{totalTrips} \times \max(\textit{time}) $$在这个时间内仅凭最慢的车一辆就能独自完成totalTrips趟其余车辆只会贡献更多因此上界一定可行。这也是 Python 实现中totalTrips * max(time)的来源。判定函数二分答案 $x$ 时计算 $f(x)$ 并与totalTrips比较若 $f(x) \ge \textit{totalTrips}$说明 $x$ 可行或已经偏大向左收缩上界否则 $x$ 不可行向右扩大下界。最终二分停下的位置就是第一个使判定为 true 的 $x$即最小可行时间也就是答案。参考实现一Go 版本仓库实际代码仓库中的实现位于 leetcode/weekly/282/c/c.go使用了标准库sort.Searchpackage main import sort // github.com/EndlessCheng/codeforces-go func minimumTime(time []int, totalTrips int) int64 { min : time[0] for _, v : range time[1:] { if v min { min v } } return int64(sort.Search(totalTrips*min, func(maxTime int) bool { tot : 0 for _, t : range time { tot maxTime / t if tot totalTrips { return true } } return false })) }需要理解sort.Search(n, f)的语义在 $[0, n)$ 内返回第一个使f(x)为 true 的 $x$要求f满足先 false 后 true。这里f(x)正是$x$ 时间内能完成至少totalTrips趟因此第一个 true 的位置即为最小可行时间无需在二分结束后再做任何修正。f(0)0totalTrips天然为 false不会干扰结果。文档原版 Go 代码使用的是更保守的上界totalTrips*1e7题目数据范围内 $\max(\textit{time})\le 10^7$ 时与totalTrips*max(time)等价直接写死可省去求 max 的循环仓库版本则进一步做了上界优化见下文。参考实现二Python 3.10 版本带 key 的一行二分原文档特别指出Python 3.10 新增带key参数的bisect_left可以把序列元素 - 判定值的映射内联进二分从而一行解决此题class Solution: def minimumTime(self, time: List[int], totalTrips: int) - int: return bisect_left(range(totalTrips * max(time)), totalTrips, keylambda x: sum(x // t for t in time))这里的技巧值得拆解range(totalTrips * max(time))是一个惰性的整数序列下标 $x$ 即时间keylambda x: sum(x // t for t in time)把下标映射成 $f(x)$bisect_left在伪序列 $f(0),f(1),\dots$上查找第一个 $\ge \textit{totalTrips}$ 的位置返回的下标就是答案。由于range是惰性求值key函数只在二分访问到的位置被调用时间/空间复杂度与手写二分完全一致是 Python 3.10 环境下的极简写法。细节与优化更紧的上界与提前退出用min(time)替换max(time)缩小二分区间一个值得注意的优化是仓库代码用totalTrips*min而不是totalTrips*max作为二分上界。理由同样成立让最快的车跑totalTrips趟所需时间为 $\textit{totalTrips}\times\min(\textit{time})$在这个时间内最快的一辆车就能独自完成totalTrips趟因此全局完成量 $\ge \textit{totalTrips}$上界可行。由于 $\min \le \max$用 min 得到的二分区间更窄二分次数更少而正确性不变。这是一个通用的二分答案优化上界只需可行不必最松选择更紧的可行上界能直接减少常数。仓库实现以一次 O(n) 的求 min 循环换取对数级区间缩小实测收益明显。判定函数内的提前退出注意c.go判定函数中这一行if tot totalTrips { return true }每累加一辆车的贡献后立刻与totalTrips比较一旦达标就提前返回避免继续遍历剩余车辆。这是典型的可行性判定短路优化在答案附近的大多数二分轮次中车辆数n可能很大短路能显著减少判定函数的平均开销。从仓库模板库 copypasta/sort.go 的二分答案题单可以看到这种判定函数内提前返回的写法是仓库中二分答案类题目的一贯风格。整数范围注意totalTrips * min(time)以及x/t的累加都可能超过 32 位整数范围。原题中time[i]与totalTrips均可达到 $10^7$ 量级乘积接近 $10^{14}$因此 Go 实现返回类型为int64判定的中间变量tot也应在语言默认整数宽度不足以容纳时使用 64 位类型仓库当前写法依赖 Go 在 64 位平台上int即 64 位跨平台提交时需留意。复杂度分析二分区间长度 $U\textit{totalTrips}\times\min(\textit{time})$sort.Search的二分次数约为 $O(\log U)$更精确地说等于 $U$ 的二进制位数bits.Len(U)见 copypasta/sort.go 的说明每次判定需遍历 $n$ 辆车最坏 $O(n)$配合短路平均更优总时间复杂度 $O(n\log(\textit{totalTrips}\cdot\min(\textit{time})))$空间复杂度 $O(1)$仅常数个临时变量。仓库测试验证leetcode/weekly/282/c/c_test.go 通过仓库自带的testutil.RunLeetCodeFuncWithExamples驱动两个官方示例输入输出验证要点time[1,2,3],totalTrips53时间 3 内车 1 跑 3 趟、车 2 跑 1 趟、车 3 跑 1 趟合计 5 趟刚好达标时间 2 内合计 $\lfloor 2/1\rfloor\lfloor 2/2\rfloor\lfloor 2/3\rfloor35$故答案确为 3time[2],totalTrips12单辆车每趟 2 单位时间跑 1 趟至少需要 2测试框架leetcode/testutil/leetcode.go负责把[][]string形式的原始用例解析为函数入参并比对输出用例数据以纯文本内嵌在测试文件中targetCaseNum : 0表示运行全部示例。你可以直接在仓库leetcode/weekly/282/c/目录下执行go test复现验证。延伸sort.Search二分答案的通用模板仓库视角本题是二分答案求最小可行值的教科书案例仓库在 copypasta/sort.go 中沉淀了配套模板与技巧值得一并掌握先 false 后 true 的要求sort.Search(n, f)要求f随下标单调翻转。本题判定$f(x)\ge totalTrips$恰好先 false 后 true直接可用。求最大值时的翻转技巧其一若目标是最大的使某条件成立的 $x$条件先 true 后 false可以对!f(x)做二分再减一或在f内部将x后判断取反条件从而复用sort.Search的单调假设。具体示例二分求int(sqrt(90))见 copypasta/sort.go。二分区间平移searchRange当答案不在 $[0,n)$ 而在 $[l,r)$ 时写l sort.Search(r-l, func(x int) bool { x l; ... })模板见 copypasta/sort.go。分类题单copypasta/sort.go 给出了二分答案的完整题型地图二分答案求最小 / 求最大 / 二分间接值 / 最小化最大值 / 最大化最小值 / 隐藏的二分并附有大量 Codeforces、AtCoder 等平台的练习题目编号可作为该技巧的进阶训练清单。小结「完成旅途的最少时间」的完整解题链条是抽象出单调的判定函数 - 选取一个一定可行的上界 - 二分第一个可行点。文档给出了最直观的totalTrips * max(time)上界与 Python 3.10 带key的一行二分仓库实现则在保持同一算法框架的前提下用totalTrips * min(time)收紧上界、并在判定内做提前退出配合sort.Search得到简洁且常数更优的 Go 解法。遇到求最小可行 X类问题最小化最大值、最大化最小值、第 K 小等都可以直接套用这套模板。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐在网格图中访问格子的最少时间Dijkstra 与二分答案 BFS 双解法剖析 —— codeforces-go 第 334 场周赛 D 题题解精读在网格图中访问格子的最少时间Dijkstra 与二分答案 BFS 双解法剖析 —— codeforces go 第 334 场周赛 D 题题解精读 本篇文科学计算最小化最大等待时间的多维 DP 与二分答案解法力扣双周赛 188 第 4 题源码级详解codeforces-go最小化最大等待时间的多维 DP 与二分答案解法力扣双周赛 188 第 4 题源码级详解codeforces go 导读本文系统讲解力扣双周赛 188 第科学计算codeforces-go 题解精讲LeetCode 周赛 326 D 题「区间内最近的质数」的筛法与二分实现codeforces go 题解精讲LeetCode 周赛 326 D 题「区间内最近的质数」的筛法与二分实现 本篇技术指南以算法竞赛模板库 codeforc科学计算上一篇推荐开源项目Immutables - Java中不可变对象的优雅解决方案下一篇CairoShell 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考