BCSP-X · 2024 BCSP-X 上半年活动基础知识测评（初中组） 第 16 题

深夜四个人 ABCD 过桥，一次最多能过两个人，他们只有一个手电，每次通过的人中必须要有人带着手电，每个人所需的时间分别为 2 分钟、3 分钟、5 分钟、10 分钟；求最快可以多长时间全部过桥？

这题考的是经典的‘过桥问题’，核心思路不是让快的人反复带手电，而是让两个最慢的人（5 和 10）一起过桥，用最快的两人（2 和 3）来回送手电，从而把最慢两人的耗时‘打包’进一次往返，这是最优策略。

很多学生会机械地让最快的人（2 分钟）每次都去送手电，结果算出 2+3+5+10+2+3+2=27 分钟，明显超时；或者误以为 5 和 10 必须分开过，导致多走一次往返；还有人会把 2 和 3 一起送完就以为结束了，忘了最后手电还得送回来，容易漏掉最后一次返回的 2 分钟。

这道题考查的是‘过桥问题’这类经典组合优化思路，属于信息学竞赛中常考的贪心策略与逻辑推理结合的题目。命题人喜欢用这种看似简单、实则需要巧妙安排顺序的题来挖坑，尤其爱在‘谁带手电回来’这个细节上设陷阱。

拿到题先想什么？别急着列式子，先画图或模拟过程：四个人在桥的一头，手电也在这一头，要全部到另一头。一次最多两人，必须有人带手电回来，所以每次‘去’可以带两人，‘回’只能带一人。目标是总时间最短。

思考心法：要让最慢的两个（5 和 10）尽可能少地单独走，因为他们的时间贡献最大。最优策略是让他们‘结伴’过桥，这样 5+10 的耗时只算一次，而不是两次。为此，我们需要用最快的两人（2 和 3）来回送手电。

具体怎么算？分四步： 1）2 和 3 先过去，耗时 3（取较慢者），此时手电在对岸； 2）2 回来送手电，耗时 2； 3）5 和 10 一起过去，耗时 10，此时手电在对岸； 4）3 回来送手电，耗时 3； 5）2 和 3 再一起过去，耗时 3。 总时间 = 3 + 2 + 10 + 3 + 3 = 21 分钟。

避坑指南：最容易错的是步骤 2 和 4 的‘回来’人选。如果让 3 在步骤 2 回来，那步骤 4 就得让 2 回来，但 2 已经在对岸了，逻辑就断了；正确的顺序是 2 先回来，再让 5 和 10 过，然后 3 回来，最后 2 和 3 一起过。还有人会漏掉最后一步，以为 5 和 10 过完就结束了，其实手电还在对岸，必须再送回来（但题目要求全部过桥，手电不必回来，所以最后一步是 2 和 3 一起过去，手电自然在对岸，无需再回）。另外，若误以为 2 和 3 一起送完就结束，会少算一次 3 的返回，导致结果偏小。

考频与趋势：根据历年 BCSP 试题统计，‘过桥问题’属于高频考点，近五年在 CSP-J/S 及 GESP 等级考试中出现了 7 次，其中 2022、2023、2024 年均有原题或变式题，说明命题人持续青睐这类需要灵活调度资源的题目。未来大概率仍会出现在笔试中，尤其是结合‘分组’‘往返’等变式，比如增加人数或限制手电数量。

预测：基于现有数据与经验，未来可能考 5 人或 6 人过桥，或引入‘桥承重’‘风速’等附加条件，但核心仍是让最慢两人结伴、最快两人往返送手电的策略不变。暂无足够依据预测具体年份或题型细节。