1. 贪心算法与Crossing River问题第一次接触信息学奥赛的同学看到Crossing River这类题目可能会觉得无从下手。这其实是一个经典的贪心算法应用场景也是NOI/OpenJudge等竞赛中经常出现的题型。我当年参加比赛时就曾被这道题卡住过后来通过反复练习才掌握了其中的精髓。贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优决策的算法策略。它不像动态规划那样考虑全局最优而是通过局部最优的选择希望最终达到全局最优。这种算法特别适合解决一些具有最优子结构特性的问题比如我们今天要讨论的渡河问题。Crossing River问题的核心是有N个人需要过河只有一条最多能载两人的船。每个人划船速度不同当两人一起划船时速度取决于较慢的那个人。我们需要设计一个渡河方案使得所有人过河的总时间最短。2. 问题分析与基本思路2.1 问题建模首先我们需要将这个问题转化为数学模型。假设有n个人需要过河他们的过河时间分别为t₁, t₂, ..., tₙ且已经按升序排列t₁ ≤ t₂ ≤ ... ≤ tₙ。船每次最多载两人过河时间由较慢的那个人决定。这个问题的难点在于船需要有人划回来所以不是简单的把人运过去就完事不同的人组合过河会产生不同的时间消耗需要合理安排来回的顺序才能最小化总时间2.2 贪心策略的选择经过分析我们发现有两种主要的贪心策略最快的人当船夫让过河最快的人(t₁)负责来回划船两个最快的人当船夫让两个最快的人(t₁和t₂)配合运送其他人这两种策略各有优劣我们需要根据具体情况选择更优的方案。下面我们通过具体例子来说明。3. 两种核心策略详解3.1 单人船夫策略这种策略的基本思路是让过河最快的人(t₁)负责所有的来回划船工作。具体步骤如下t₁和tᵢ一起过河耗时tᵢt₁单独划船回来耗时t₁t₁和tⱼ一起过河耗时tⱼt₁单独划船回来耗时t₁这样运送两个人的总时间为2t₁ tᵢ tⱼ举个例子假设四个人的过河时间为1、2、5、10分钟1和10过河10分钟1回来1分钟1和5过河5分钟1回来1分钟 总时间10 1 5 1 17分钟3.2 双人船夫策略这种策略的基本思路是让两个最快的人(t₁和t₂)配合运送其他人。具体步骤如下t₁和t₂一起过河耗时t₂t₁单独划船回来耗时t₁tᵢ和tⱼ一起过河耗时tⱼt₂单独划船回来耗时t₂这样运送两个人的总时间为t₁ 2t₂ tⱼ还是用1、2、5、10的例子1和2过河2分钟1回来1分钟5和10过河10分钟2回来2分钟 总时间2 1 10 2 15分钟看起来这个策略比前一个更好但实际上我们还需要考虑后续步骤。完整的解决方案需要结合这两种策略。4. 最优策略的选择与实现4.1 策略比较与选择在实际解题时我们需要比较两种策略的优劣选择更优的方案。对于每次运送最慢的两个人我们应该比较单人船夫策略2t₁ tₙ tₙ₋₁双人船夫策略t₁ 2t₂ tₙ选择两者中较小的那个方案。4.2 算法实现步骤基于以上分析我们可以总结出完整的算法步骤将所有过河时间排序升序每次处理剩余人中最慢的两个计算两种策略的时间选择较小的方案累计总时间移除已过河的两人处理剩余的特殊情况3人、2人或1人4.3 边界情况处理在实现算法时需要特别注意以下几种边界情况剩余3人最佳方案是t₁t₂t₃t₁和t₃过河t₃t₁回来t₁t₁和t₂过河t₂剩余2人直接一起过河时间为较慢者(t₂)只有1人直接过河时间为t₁5. 代码实现与优化5.1 基础实现以下是基于贪心策略的C实现代码#include bits/stdc.h using namespace std; int main() { int T, n; cin T; while(T--) { cin n; vectorint t(n); for(int i0; in; i) cin t[i]; sort(t.begin(), t.end()); int total 0; while(n 3) { int plan1 2*t[0] t[n-1] t[n-2]; int plan2 t[0] 2*t[1] t[n-1]; total min(plan1, plan2); n - 2; } if(n 3) total t[0] t[1] t[2]; else if(n 2) total t[1]; else total t[0]; cout total endl; } return 0; }5.2 性能优化虽然题目中n≤1000这个算法已经是O(nlogn)的复杂度主要来自排序但在实际竞赛中还可以做以下优化使用更快的排序算法如内建的sort避免不必要的容器操作使用更快的输入输出方式如scanf/printf或关闭同步的cin/cout6. 数学证明与正确性分析6.1 贪心选择性质为什么这种贪心策略能得到最优解我们可以从以下几个方面来理解每次运送最慢的两个人是合理的因为他们对总时间的贡献最大让最快的人多次往返是最经济的因为这样能最小化空船时间两种策略的比较确保了每次选择都是局部最优的6.2 最优子结构这个问题具有最优子结构性质整个问题的最优解包含了子问题的最优解。也就是说如果我们能找到运送两个人的最优方案那么重复这个过程就能得到整体的最优解。7. 变种与扩展7.1 不同人数的变种单人船每次只能载一人总时间就是所有人时间之和三人船每次能载三人需要设计新的策略不同容量的船混合载人容量增加问题复杂度7.2 其他约束条件夜间过河可能需要考虑照明问题不同方向的河流顺流和逆流速度不同多人协作划船速度计算方式更复杂8. 实际应用与思维训练Crossing River问题虽然看似简单但它能很好地训练我们的算法思维问题分解能力将复杂问题分解为可处理的子问题策略比较能力评估不同方案的优劣边界处理能力考虑各种特殊情况优化思维寻找更高效的解决方案在实际软件开发中类似的资源调度问题很常见比如任务分配、负载均衡等。理解这类问题的解法对培养解决实际工程问题的能力很有帮助。