1. 题目到底在问什么以及贪心的直觉陷阱1.1 题意速览n个人、一只手电筒的约束经典OJ题目POJ 1700题面很短但第一次做的时候我差点被它“坑”出心理阴影n个人晚上过桥桥上一次最多走两个人而且手里必须有手电筒才能过桥。手电筒只有一个所以只要还有人在这边就必须有人把电筒送回来。每个人过桥耗时不同两人一起过桥时按耗时较长的那个人算。题目要你求所有人全部到达对岸的最短总时间。举个最经典的例子四个人速度分别是1、2、5、10。正确答案是17分钟很多人第一次算会算成19分钟。为什么因为大家会本能地想让速度最快的人当“摆渡员”一趟趟接送所有人。这个思路听起来非常合理最快的人跑腿代价最小嘛但实际算一下就知道不是最优。1先陪2过去耗时21回来耗时11再陪5过去耗时51回来耗时11再陪10过去耗时10总共21511019。而真正的最优方案是1和2先过去耗时21回来耗时15和10一起过去耗时102回来耗时2最后1和2再过去耗时2合计17。这道题适合什么人看两个群体。一是在刷算法题、想搞懂贪心策略到底“贪”在哪的入门选手二是已经会写代码但每次遇到这题都得靠背结论、过段时间又忘了的人。这篇不是简单给结论而是把两个核心策略的账本拆开告诉你为什么这么分、什么时候选哪个、三段式代码怎么写以及提交时容易翻车的边界坑。1.2 直觉方案为什么经常给出错误答案大多数人把“快速渡河”理解成了“让最快的负责跑腿”这本质上是把问题简化成了单变量优化护送者速度越快返程成本越低。但这里有个隐藏变量被忽略了——被护送的人到底怎么组合过河。还是用1、2、5、10这个例子。如果坚持让1当专职司机代价是1要反复跑三趟中间还要承担所有人各自的“单项耗时”等于把慢速人员的耗时摊到每一趟里。而最优方案里面5和10是两个人一起过桥的耗时虽然由最慢的10决定但这一趟同时解决了两个人省掉了一整个来回的返程成本。换句话说真正的代价模型不是“谁快谁承担返还”而是“哪些慢的人可以打包、打包后能省下几个返程”。很多贪心题是这样直觉能给你一个还算不错的方案但拿不到最优。POJ 1700是比较典型的“双策略贪心”它不是在一条路上做局部选择而是每轮要在两条不同的路之间挑一条。想靠感觉一次蒙对基本不可能。2. 两类运输策略的账本谁当“跑腿”最划算2.1 策略一最快的“单陪”模式把所有人按过桥速度从小到大排序最快的是a[0]次快的是a[1]当前剩下的人里最慢的是a[M-1]倒数第二慢的是a[M-2]。策略一很直观让最快的a[0]当专职护送员一次陪一个最慢的人过桥然后马上把手电筒送回来。处理两个最慢的人时过程是这样的a[0]陪a[M-1]过河耗时按a[M-1]算a[0]独自回来耗时按a[0]算a[0]再陪a[M-2]过河耗时按a[M-2]算a[0]再独自回来耗时按a[0]算。一轮处理两个最慢的人总成本是 a[M-1] a[M-2] 2 * a[0]。为什么这里要“一轮处理两个”因为这道题的常规做法就是每轮淘汰两个最慢的人把剩余人数减少2直到剩下不超过3个人再单独收尾。策略一的优点是逻辑极其简单代码就是把当前最慢的两个人分别和最快的人一起送过去。但它有个很隐蔽的弱点a[0]作为最快的人一个人要跑四趟。如果这个“最快”和“第二快”差距很大比如a[0]1、a[1]2那还好但如果a[0]10、a[1]11后面还有两个超级慢的人那让a[0]来回跑成本其实非常恐怖。2.2 策略二两个最快者的“接应”模式策略二的思路就稍微反直觉了不是让最快的人一直跑而是让最快的两个人打配合。具体过程是a[0]和a[1]先一起过河耗时按a[1]算a[0]带着手电筒回来耗时按a[0]算当前最慢的a[M-1]和倒数第二慢的a[M-2]一起过河耗时按a[M-1]算a[1]在对岸把手电筒送回来耗时按a[1]算。一轮下来总成本是 a[0] 2 * a[1] a[M-1]。注意这一步和策略一最大的区别两个最慢的人是一起过河的所以只需要支付一次“最慢时间”不用反复让速度快的人陪他们单独走。而回来送手电筒的活被拆给了a[0]和a[1]两个人完成a[1]不必来回两趟只用在对岸等着再回来一次就行。可以拿生活中的拼车理解策略一像是一辆专车分别送两个客户回家司机每趟都要空车返回策略二像是先派一个快车手去把另一辆车钥匙拿过来然后两辆车同时接人一辆车留下做接应。虽然策略二多了a[1]的一次时间消耗但它把a[0]的重复返程次数压下来了还把两个慢乘客“拼车”成了一个组合。两种策略到底谁更省完全取决于速度分布。有时候策略一赢有时候策略二赢这就是POJ 1700比普通贪心题更麻烦的地方——你必须在不同情况下做真正的“两案比较”。3. 策略分界线的推导一眼看出选A还是选B3.1 一次过两人的成本比较把两种策略的成本放在一起看策略一C1 a[M-1] a[M-2] 2 * a[0]策略二C2 a[M-1] a[0] 2 * a[1]两者都包含了同一个最慢时间 a[M-1]可以抵消掉。所以真正要比的是 a[M-2] 2 * a[0] 和 a[0] 2 * a[1] 哪个更小。移项之后得到分界条件当 a[M-2] a[0] 2 * a[1] 时策略一更好否则策略二更好。这个式子很值得品味。最慢的那个人a[M-1]在这个判断里完全不影响选哪个策略因为不管走那条路最慢的那个人都得付出一次最慢时间。真正决定胜负的是第二慢的人a[M-2]和次快的人a[1]之间的速度关系。如果第二慢的人足够慢让a[0]陪他单独走一趟的收益更大选择策略一如果第二慢的人和a[1]差距不大那不如让两个最慢的人一起走用a[1]来回跑腿选择策略二。我把这个分界条件抄在纸上很久后来发现它就是一句话第二慢比次快“慢得足够多”就单陪否则就组团。3.2 循环中的决策与边界从M3开始每轮都拿四个关键角色来比较最快a[0]、次快a[1]、当前第二慢a[M-2]、当前最慢a[M-1]。选好本轮策略后把两个最慢的人从剩余名单里删掉M减2重复循环直到M不超过3。为什么每轮固定干掉两个最慢的人因为无论怎么安排当前最慢的那个人都一定得过去而且必须在某个时间点过去。既然一定要过去那让他在当前这一轮走就是“局部最优操作”。把他和倒数第二慢的人打包或者分别送过去剩下的子问题仍然是一个同构的小规模渡河问题。这就是这道题可以放心用贪心循环的基础。M等于3的时候要单独收尾a[0]先陪a[1]过去a[0]回来再陪a[2]过去。总时间是 a[0] a[1] a[2]。这其实也能套进一种“护送式”的直觉里三个人时没必要采取复杂接应因为最慢的人一旦提前过去还得有人回来反而多绕路。3.3 为什么局部最优能凑成全局最优很多初学者看到这种“每轮局部选優”的套路会问为什么这一步选了最快方式后面不会导致更慢答案是子问题结构没有变。无论你是按策略一还是策略二处理两个最慢的人送完之后剩下的M-2个人仍然在同一岸集结手里仍然只有一只手电筒规则完全一样。这时候你面对的是“M-2个人的快速渡河问题”跟原问题同构。正因为每一步都能安全地去掉两个“历史包袱”全局最优才能这样拼出来。如果贪心去处理最快的人而不是最慢的人问题结构反而会立刻崩掉——因为最慢的人始终是最大的障碍不先解决他会一直拖累后面所有轮次。我在理解这题时还发现一个反直觉点最优方案不一定是每一步“当下花费最少”的方案。比如有时策略一这一轮看着比较便宜但它会让下一轮剩余人员组合变差只不过在这个问题里面不会发生这种情况因为两个最慢的一次性淘汰后剩余人员结构没有历史依赖。这也是这道题“贪”得合理的关键。4. 代码实现与提交中容易翻车的细节4.1 完整示例代码先给出一个能直接跑的C版本代码里注释比较全#include bits/stdc.h using namespace std; int main() { int T; while (cin T) { while (T--) { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long ans 0; int left n; // 仍在原岸的人数 while (left 3) { // 当前最慢的人 a[left-1] // 当前第二慢的人 a[left-2] // 策略一最快的人分别陪两个最慢的人过桥 long long cost1 a[left - 1] a[left - 2] 2 * a[0]; // 策略二最快和次快先过最快返回两个最慢一起过次快返回 long long cost2 a[left - 1] a[0] 2 * a[1]; ans min(cost1, cost2); left - 2; } if (left 3) { ans a[0] a[1] a[2]; } else if (left 2) { ans a[1]; } else if (left 1) { ans a[0]; } cout ans \n; } } return 0; }这段代码的核心就是每轮从最慢端“切除”两个人直到剩下3人以内。复杂度是O(n log n)排序是瓶颈对所有竞赛场景都够用。left变量用来说明剩余人数比直接操作数组下标要直观得多也更容易避免越界。4.2 排序、下标、边界条件这类老坑提交POJ 1700时最常见的错误我总结下来有三个。第一个是排序方向。这道题默认升序排序a[0]是速度最快的人。如果你习惯降序排序那么后面所有下标含义都会颠倒。建议先定一个规矩数组从小到大排快速的人站在最前面这样脑内推演时不会乱。第二个是三个人的特判。如果不做left3的特判直接在循环里硬套策略一和策略二最典型的结果是答案凭空变大。因为四人以上的策略设计了两轮“跨岸接应”而三个人时最优路径根本没有这么多往返。很多人把这道题写成背模板结果遇到n3的小数据就挂。第三个是数据类型的警惕。POJ 1700原题的数据量不算巨大但如果是类似变体速度值可能很大手电筒来回次数也不少int在累计时是有可能溢出的。我习惯直接用long long防一手总没坏处。另外多组输入怎么处理也要注意。我见过有人只读一组数据就提交本地样例全过一交到OJ就错。用while(cinT)这种写法读多组数据是竞赛基操有些在线平台还会把T给在数据第一行别漏。4.3 多组输入与代码可读性代码可读性这事很多人觉得竞赛代码无所谓但我自己被坑过写长了之后忘了cost1和cost2分别对应什么策略调试时想半天。所以我后来写这类题都习惯把“一轮成本”的计算注释写清楚甚至直接命名成costSingle和costGroup一眼就知道谁是谁。写完之后建议在本地至少跑这几个样例输入期望输出4171 2 5 10171一个人的话输出它自己2两个人按慢的那个算1 2 3 4 5可以手算验证这四个样例覆盖了最关键的几条分支循环正常展开、单人多人的特殊分支、以及典型的1、2、5、10经典数据。我在做这类题的时候习惯把样例手算出来的答案写在注释里再跑代码对比。这样能快速排除公式抄错的问题。5. 证明套路、同类题迁移与实际场景5.1 这类贪心的通用证明模板想说服自己“这题贪心成立”可以走一个简单的调整法。假设存在一个最优方案看当前最慢的人a[M-1]是什么时候过河的以及当时手电筒在谁手里。如果最慢的人是和倒数第二慢的人之外的某个中速人一起过的那么总可以把这一趟调整为“和倒数第二慢的人一起过”或者“用策略二的方案替代”而总时间不会变差。因为所有其他过河事件发生的顺序和人员组合都不受影响唯独返程的那个人可能要变成a[0]或a[1]而这两个人的速度排名已经决定了他们是“可选返程者”里成本最低的一批。再进一步任何最优方案中两个最慢的人过河的时机总可以被“归一化”到两种模式要么最慢的人由最快的人单独护送两次要么两个最慢的人被合并为一次过河且由最快/次快轮流接送。这就和两种策略一一对应了。一旦代码里每轮都按这两条里的最小值执行就等同于在最优方案上不断做局部裁剪最后当然得到全局最优。说得更粗糙一点这类题的证明思路从来不是从正面找全局下界而是假设一个任意最优解然后证明它可以被“调整”成某种固定形态并且调整过程不增加成本。一旦找到固定形态问题就变成了有限个候选方案取最小值贪心选择自然就合法了。5.2 变体题目与迁移思路POJ 1700这种“多人共用一束光过桥”模型在竞赛里有一大堆变体。最常见的是把“最多两人”改成“最多三人”这时候策略就不止两种了你得把最慢的三人打包、两人打包、单人分别送各种组合全部算一遍然后再比大小。思路还是同一个先把最慢的几个人从名单里裁掉但要对“怎么裁”做枚举。还有一种变体是把手电筒换成“运货小车”人过去不用回来只有小车需要回到起点。这种题反而比原题简单因为再也不存在“跑腿人”成本了问题退化成尽量把慢的人两两组合在一起过河。我曾经遇到一个题看起来很像POJ 1700但实际上规则是“过河者必须按固定分组顺序排列”结果直接套1700模板就错了。这说明读规则永远比背模板重要。在实际工作场景里这类模型也偶尔会冒出来。比如物流仓库里有一批货要通过一个需要人工押运的通道通道一次只能走两批货押运员必须回到起点才能继续下一趟。这时候谁当押运员、哪些货最后走本质上就是速度换成货物流转时间后的同一道题。还有工厂流水线里某道工序需要一名操作员陪同一批零件完成跨区运输同样可以套用“两个最快者接应”的思路。5.3 遇到类似题怎么快速定位我后来刷题遇到这类题目会先在脑子里过三个问题第一是不是只有一个“通行许可”或者“照明工具”第二是不是必须有东西或者人回到原岸第三代价是不是按小组里最慢的成员算如果三个回答都是“是”那基本就是POJ 1700的亲戚。确认模型之后不要急着写循环。先把四个关键速度值拉出来比一比最快、次快、第二慢、最慢。手算一轮两种策略的cost感受一下这个数据倾向于单陪还是组团再去写代码。我见到很多选手在这题上翻车都是因为第一件事就写while循环写到一半才发现“哦这个例子原来应该走策略二”然后又要返工。最后再分享一个实操小技巧你自己写完了代码可以随机生成n在1到6之间的几组速度数组然后用深搜把所有合法方案都算一遍把你的贪心答案和深搜答案做对比。只要随机数据够多哪种边界理解有偏差会立刻暴露。这个“贪心对拍法”我在很多类似渡河题上都用过比对着别人的题解猜边界靠谱多了。
1. 题目到底在问什么以及贪心的直觉陷阱1.1 题意速览n个人、一只手电筒的约束经典OJ题目POJ 1700题面很短但第一次做的时候我差点被它“坑”出心理阴影n个人晚上过桥桥上一次最多走两个人而且手里必须有手电筒才能过桥。手电筒只有一个所以只要还有人在这边就必须有人把电筒送回来。每个人过桥耗时不同两人一起过桥时按耗时较长的那个人算。题目要你求所有人全部到达对岸的最短总时间。举个最经典的例子四个人速度分别是1、2、5、10。正确答案是17分钟很多人第一次算会算成19分钟。为什么因为大家会本能地想让速度最快的人当“摆渡员”一趟趟接送所有人。这个思路听起来非常合理最快的人跑腿代价最小嘛但实际算一下就知道不是最优。1先陪2过去耗时21回来耗时11再陪5过去耗时51回来耗时11再陪10过去耗时10总共21511019。而真正的最优方案是1和2先过去耗时21回来耗时15和10一起过去耗时102回来耗时2最后1和2再过去耗时2合计17。这道题适合什么人看两个群体。一是在刷算法题、想搞懂贪心策略到底“贪”在哪的入门选手二是已经会写代码但每次遇到这题都得靠背结论、过段时间又忘了的人。这篇不是简单给结论而是把两个核心策略的账本拆开告诉你为什么这么分、什么时候选哪个、三段式代码怎么写以及提交时容易翻车的边界坑。1.2 直觉方案为什么经常给出错误答案大多数人把“快速渡河”理解成了“让最快的负责跑腿”这本质上是把问题简化成了单变量优化护送者速度越快返程成本越低。但这里有个隐藏变量被忽略了——被护送的人到底怎么组合过河。还是用1、2、5、10这个例子。如果坚持让1当专职司机代价是1要反复跑三趟中间还要承担所有人各自的“单项耗时”等于把慢速人员的耗时摊到每一趟里。而最优方案里面5和10是两个人一起过桥的耗时虽然由最慢的10决定但这一趟同时解决了两个人省掉了一整个来回的返程成本。换句话说真正的代价模型不是“谁快谁承担返还”而是“哪些慢的人可以打包、打包后能省下几个返程”。很多贪心题是这样直觉能给你一个还算不错的方案但拿不到最优。POJ 1700是比较典型的“双策略贪心”它不是在一条路上做局部选择而是每轮要在两条不同的路之间挑一条。想靠感觉一次蒙对基本不可能。2. 两类运输策略的账本谁当“跑腿”最划算2.1 策略一最快的“单陪”模式把所有人按过桥速度从小到大排序最快的是a[0]次快的是a[1]当前剩下的人里最慢的是a[M-1]倒数第二慢的是a[M-2]。策略一很直观让最快的a[0]当专职护送员一次陪一个最慢的人过桥然后马上把手电筒送回来。处理两个最慢的人时过程是这样的a[0]陪a[M-1]过河耗时按a[M-1]算a[0]独自回来耗时按a[0]算a[0]再陪a[M-2]过河耗时按a[M-2]算a[0]再独自回来耗时按a[0]算。一轮处理两个最慢的人总成本是 a[M-1] a[M-2] 2 * a[0]。为什么这里要“一轮处理两个”因为这道题的常规做法就是每轮淘汰两个最慢的人把剩余人数减少2直到剩下不超过3个人再单独收尾。策略一的优点是逻辑极其简单代码就是把当前最慢的两个人分别和最快的人一起送过去。但它有个很隐蔽的弱点a[0]作为最快的人一个人要跑四趟。如果这个“最快”和“第二快”差距很大比如a[0]1、a[1]2那还好但如果a[0]10、a[1]11后面还有两个超级慢的人那让a[0]来回跑成本其实非常恐怖。2.2 策略二两个最快者的“接应”模式策略二的思路就稍微反直觉了不是让最快的人一直跑而是让最快的两个人打配合。具体过程是a[0]和a[1]先一起过河耗时按a[1]算a[0]带着手电筒回来耗时按a[0]算当前最慢的a[M-1]和倒数第二慢的a[M-2]一起过河耗时按a[M-1]算a[1]在对岸把手电筒送回来耗时按a[1]算。一轮下来总成本是 a[0] 2 * a[1] a[M-1]。注意这一步和策略一最大的区别两个最慢的人是一起过河的所以只需要支付一次“最慢时间”不用反复让速度快的人陪他们单独走。而回来送手电筒的活被拆给了a[0]和a[1]两个人完成a[1]不必来回两趟只用在对岸等着再回来一次就行。可以拿生活中的拼车理解策略一像是一辆专车分别送两个客户回家司机每趟都要空车返回策略二像是先派一个快车手去把另一辆车钥匙拿过来然后两辆车同时接人一辆车留下做接应。虽然策略二多了a[1]的一次时间消耗但它把a[0]的重复返程次数压下来了还把两个慢乘客“拼车”成了一个组合。两种策略到底谁更省完全取决于速度分布。有时候策略一赢有时候策略二赢这就是POJ 1700比普通贪心题更麻烦的地方——你必须在不同情况下做真正的“两案比较”。3. 策略分界线的推导一眼看出选A还是选B3.1 一次过两人的成本比较把两种策略的成本放在一起看策略一C1 a[M-1] a[M-2] 2 * a[0]策略二C2 a[M-1] a[0] 2 * a[1]两者都包含了同一个最慢时间 a[M-1]可以抵消掉。所以真正要比的是 a[M-2] 2 * a[0] 和 a[0] 2 * a[1] 哪个更小。移项之后得到分界条件当 a[M-2] a[0] 2 * a[1] 时策略一更好否则策略二更好。这个式子很值得品味。最慢的那个人a[M-1]在这个判断里完全不影响选哪个策略因为不管走那条路最慢的那个人都得付出一次最慢时间。真正决定胜负的是第二慢的人a[M-2]和次快的人a[1]之间的速度关系。如果第二慢的人足够慢让a[0]陪他单独走一趟的收益更大选择策略一如果第二慢的人和a[1]差距不大那不如让两个最慢的人一起走用a[1]来回跑腿选择策略二。我把这个分界条件抄在纸上很久后来发现它就是一句话第二慢比次快“慢得足够多”就单陪否则就组团。3.2 循环中的决策与边界从M3开始每轮都拿四个关键角色来比较最快a[0]、次快a[1]、当前第二慢a[M-2]、当前最慢a[M-1]。选好本轮策略后把两个最慢的人从剩余名单里删掉M减2重复循环直到M不超过3。为什么每轮固定干掉两个最慢的人因为无论怎么安排当前最慢的那个人都一定得过去而且必须在某个时间点过去。既然一定要过去那让他在当前这一轮走就是“局部最优操作”。把他和倒数第二慢的人打包或者分别送过去剩下的子问题仍然是一个同构的小规模渡河问题。这就是这道题可以放心用贪心循环的基础。M等于3的时候要单独收尾a[0]先陪a[1]过去a[0]回来再陪a[2]过去。总时间是 a[0] a[1] a[2]。这其实也能套进一种“护送式”的直觉里三个人时没必要采取复杂接应因为最慢的人一旦提前过去还得有人回来反而多绕路。3.3 为什么局部最优能凑成全局最优很多初学者看到这种“每轮局部选優”的套路会问为什么这一步选了最快方式后面不会导致更慢答案是子问题结构没有变。无论你是按策略一还是策略二处理两个最慢的人送完之后剩下的M-2个人仍然在同一岸集结手里仍然只有一只手电筒规则完全一样。这时候你面对的是“M-2个人的快速渡河问题”跟原问题同构。正因为每一步都能安全地去掉两个“历史包袱”全局最优才能这样拼出来。如果贪心去处理最快的人而不是最慢的人问题结构反而会立刻崩掉——因为最慢的人始终是最大的障碍不先解决他会一直拖累后面所有轮次。我在理解这题时还发现一个反直觉点最优方案不一定是每一步“当下花费最少”的方案。比如有时策略一这一轮看着比较便宜但它会让下一轮剩余人员组合变差只不过在这个问题里面不会发生这种情况因为两个最慢的一次性淘汰后剩余人员结构没有历史依赖。这也是这道题“贪”得合理的关键。4. 代码实现与提交中容易翻车的细节4.1 完整示例代码先给出一个能直接跑的C版本代码里注释比较全#include bits/stdc.h using namespace std; int main() { int T; while (cin T) { while (T--) { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) { cin a[i]; } sort(a.begin(), a.end()); long long ans 0; int left n; // 仍在原岸的人数 while (left 3) { // 当前最慢的人 a[left-1] // 当前第二慢的人 a[left-2] // 策略一最快的人分别陪两个最慢的人过桥 long long cost1 a[left - 1] a[left - 2] 2 * a[0]; // 策略二最快和次快先过最快返回两个最慢一起过次快返回 long long cost2 a[left - 1] a[0] 2 * a[1]; ans min(cost1, cost2); left - 2; } if (left 3) { ans a[0] a[1] a[2]; } else if (left 2) { ans a[1]; } else if (left 1) { ans a[0]; } cout ans \n; } } return 0; }这段代码的核心就是每轮从最慢端“切除”两个人直到剩下3人以内。复杂度是O(n log n)排序是瓶颈对所有竞赛场景都够用。left变量用来说明剩余人数比直接操作数组下标要直观得多也更容易避免越界。4.2 排序、下标、边界条件这类老坑提交POJ 1700时最常见的错误我总结下来有三个。第一个是排序方向。这道题默认升序排序a[0]是速度最快的人。如果你习惯降序排序那么后面所有下标含义都会颠倒。建议先定一个规矩数组从小到大排快速的人站在最前面这样脑内推演时不会乱。第二个是三个人的特判。如果不做left3的特判直接在循环里硬套策略一和策略二最典型的结果是答案凭空变大。因为四人以上的策略设计了两轮“跨岸接应”而三个人时最优路径根本没有这么多往返。很多人把这道题写成背模板结果遇到n3的小数据就挂。第三个是数据类型的警惕。POJ 1700原题的数据量不算巨大但如果是类似变体速度值可能很大手电筒来回次数也不少int在累计时是有可能溢出的。我习惯直接用long long防一手总没坏处。另外多组输入怎么处理也要注意。我见过有人只读一组数据就提交本地样例全过一交到OJ就错。用while(cinT)这种写法读多组数据是竞赛基操有些在线平台还会把T给在数据第一行别漏。4.3 多组输入与代码可读性代码可读性这事很多人觉得竞赛代码无所谓但我自己被坑过写长了之后忘了cost1和cost2分别对应什么策略调试时想半天。所以我后来写这类题都习惯把“一轮成本”的计算注释写清楚甚至直接命名成costSingle和costGroup一眼就知道谁是谁。写完之后建议在本地至少跑这几个样例输入期望输出4171 2 5 10171一个人的话输出它自己2两个人按慢的那个算1 2 3 4 5可以手算验证这四个样例覆盖了最关键的几条分支循环正常展开、单人多人的特殊分支、以及典型的1、2、5、10经典数据。我在做这类题的时候习惯把样例手算出来的答案写在注释里再跑代码对比。这样能快速排除公式抄错的问题。5. 证明套路、同类题迁移与实际场景5.1 这类贪心的通用证明模板想说服自己“这题贪心成立”可以走一个简单的调整法。假设存在一个最优方案看当前最慢的人a[M-1]是什么时候过河的以及当时手电筒在谁手里。如果最慢的人是和倒数第二慢的人之外的某个中速人一起过的那么总可以把这一趟调整为“和倒数第二慢的人一起过”或者“用策略二的方案替代”而总时间不会变差。因为所有其他过河事件发生的顺序和人员组合都不受影响唯独返程的那个人可能要变成a[0]或a[1]而这两个人的速度排名已经决定了他们是“可选返程者”里成本最低的一批。再进一步任何最优方案中两个最慢的人过河的时机总可以被“归一化”到两种模式要么最慢的人由最快的人单独护送两次要么两个最慢的人被合并为一次过河且由最快/次快轮流接送。这就和两种策略一一对应了。一旦代码里每轮都按这两条里的最小值执行就等同于在最优方案上不断做局部裁剪最后当然得到全局最优。说得更粗糙一点这类题的证明思路从来不是从正面找全局下界而是假设一个任意最优解然后证明它可以被“调整”成某种固定形态并且调整过程不增加成本。一旦找到固定形态问题就变成了有限个候选方案取最小值贪心选择自然就合法了。5.2 变体题目与迁移思路POJ 1700这种“多人共用一束光过桥”模型在竞赛里有一大堆变体。最常见的是把“最多两人”改成“最多三人”这时候策略就不止两种了你得把最慢的三人打包、两人打包、单人分别送各种组合全部算一遍然后再比大小。思路还是同一个先把最慢的几个人从名单里裁掉但要对“怎么裁”做枚举。还有一种变体是把手电筒换成“运货小车”人过去不用回来只有小车需要回到起点。这种题反而比原题简单因为再也不存在“跑腿人”成本了问题退化成尽量把慢的人两两组合在一起过河。我曾经遇到一个题看起来很像POJ 1700但实际上规则是“过河者必须按固定分组顺序排列”结果直接套1700模板就错了。这说明读规则永远比背模板重要。在实际工作场景里这类模型也偶尔会冒出来。比如物流仓库里有一批货要通过一个需要人工押运的通道通道一次只能走两批货押运员必须回到起点才能继续下一趟。这时候谁当押运员、哪些货最后走本质上就是速度换成货物流转时间后的同一道题。还有工厂流水线里某道工序需要一名操作员陪同一批零件完成跨区运输同样可以套用“两个最快者接应”的思路。5.3 遇到类似题怎么快速定位我后来刷题遇到这类题目会先在脑子里过三个问题第一是不是只有一个“通行许可”或者“照明工具”第二是不是必须有东西或者人回到原岸第三代价是不是按小组里最慢的成员算如果三个回答都是“是”那基本就是POJ 1700的亲戚。确认模型之后不要急着写循环。先把四个关键速度值拉出来比一比最快、次快、第二慢、最慢。手算一轮两种策略的cost感受一下这个数据倾向于单陪还是组团再去写代码。我见到很多选手在这题上翻车都是因为第一件事就写while循环写到一半才发现“哦这个例子原来应该走策略二”然后又要返工。最后再分享一个实操小技巧你自己写完了代码可以随机生成n在1到6之间的几组速度数组然后用深搜把所有合法方案都算一遍把你的贪心答案和深搜答案做对比。只要随机数据够多哪种边界理解有偏差会立刻暴露。这个“贪心对拍法”我在很多类似渡河题上都用过比对着别人的题解猜边界靠谱多了。
