CSP-J 入门级 · CSP 2021 入门级第一轮 第 15 题

有四个人要从 A 点坐一条船过河到 B 点，船一开始在 A 点。该船一次最多可坐两个人。 已知这四个人中每个人独自坐船的过河时间分别为 $1, 2, 4, 8$，且两个人坐船的过河时间为两人独自过河时间的较大者。则最短（ ）时间可以让四个人都过河到 B 点（包括从 B 点把船开回 A 点的时间）。

别光盯着最快的人来回送，这道题的破局点在于：当最慢的两个家伙要过河时，是让他们自己走（最快的人陪他们）划算，还是让最快的两个人先过去、把船送回来再让他们走更划算？算一下这两个方案的差价，选小的那个就能把总时间压到最低。

学生最容易掉进的坑就是机械地认为‘每次都得最快的人把船开回来’。其实过河问题里，最慢两人过河时，有两种经典策略：一是派最快的人陪他们过去再回来，二是派最快两人过去、最快回来、最慢两人过去、次快回来。很多人会漏掉第二种，或者死算第一种，导致算出16分钟或17分钟。另外，还有人会忘记最后一步船必须有人从B点开回A点接剩下的人，或者误以为只要所有人到对岸就行，忽略了往返的船费。

考察知识点：贪心算法 — 过河问题

概念定义： 过河问题：n个人过河，船最多坐2人，过河时间取较慢者的时间，需要有人把船开回来。

最优策略： 两种子策略结合使用： 策略A：最快者来回送——1和某过去，1回来，耗时=t₁+max(t₁,tᵢ)=t₁+tᵢ 策略B：最快两人做渡轮——1和2过去，1回来，最慢两人过去，2回来，耗时=t₂+t₁+tⱼ+t₂

逐步推导： 时间：1, 2, 4, 8

次慢(4)和最慢(8)的过河： 策略A：1和8过去(8min)，1回来(1min) → 9min 策略B：1和2过去(2min)，1回来(1min)，4和8过去(8min)，2回来(2min) → 13min 策略B更好。

然后剩下1,2（在A岸）： 1和2过(2min) → 2min

总时间 = 13+2 = 15min

或者另外一种安排： 1+2过(2min)，1回(1min) 4+8过(8min)，2回(2min) 1+2过(2min) 总=2+1+8+2+2=15min ✅

考频与趋势： 贪心算法在题库中已考过71题，覆盖9个考试级别。从逐年分布看，2010年1题、2019年3题、2020年3题、2021年2题、2022年1题、2023年3题、2024年16题、2025年12题、2026年24题、null年6题。分赛事来看，GESP五级25题、六级13题、入门级12题、八级8题、七级5题、提高级5题、三级1题、四级1题、NOIP普及组初赛1题。

预测： 鉴于2024年和2025年贪心类题目数量显著上升（2024年16题、2025年12题），且近年来CSP入门级和GESP五级、六级持续高频考查，预计未来两年（2026-2027）过河问题这类经典贪心模型仍将是高频考点，尤其是涉及多人过河、船载限制和往返策略优化的变式题。暂无足够依据预测具体年份和题型，但建议重点掌握上述两种过河策略及其比较方法。