从POJ到CSP-J：手把手带你用C++实现‘Crossing River’贪心算法（附测试数据生成技巧）

从POJ到CSP-J：手把手带你用C++实现‘Crossing River’贪心算法（附测试数据生成技巧）

在信息学竞赛的备考过程中，经典算法题的实战演练往往能起到事半功倍的效果。今天我们要深入探讨的"Crossing River"问题，正是这样一个横跨POJ和CSP-J两大平台的经典贪心算法案例。无论你是在准备NOI系列赛事，还是正在备战CSP-J/S认证，掌握这道题的精髓都将为你的竞赛之路添砖加瓦。

这道题看似简单——N个人要过河，只有一条最多载两人的船，每个人划船速度不同——但其中蕴含的贪心策略却十分巧妙。更重要的是，在实际竞赛中，我们不仅要写出正确的代码，还需要确保它能应对各种边界情况和压力测试。本文将带你从零开始，一步步实现这个算法，并教你如何生成全面的测试数据来验证你的解决方案。

1. 问题分析与贪心策略设计

1.1 理解题目本质

"Crossing River"问题的核心在于如何在有限的运输能力下（每次最多两人），合理安排人员的过河顺序，使得总时间最短。关键在于：

• 两人同船时，速度以慢者为准
• 船必须有人划回来（除非所有人都已过河）
• 需要计算的是总时间，而非单次运输时间

这个问题在POJ和国内教材中的描述略有差异。例如，OpenJudge的英文原题明确给出了数据范围限制（T≤20，n≤1000），而一些国内教材可能省略了这些细节。在实际竞赛中，这种细微差别可能导致程序无法通过某些测试用例，因此我们必须仔细阅读题目描述。

1.2 贪心策略的两种方案

经过分析，我们发现最优解通常来自以下两种运输方案的组合：

方案一：最快者运输模式

1. 最快的两人a和b过河（时间：b）
2. a划船返回（时间：a）
3. 最慢的两人c和d过河（时间：d）
4. b划船返回（时间：b） 总时间：a + 2b + d

方案二：双快运输模式

1. a和最快的b过河（时间：b）
2. a返回（时间：a）
3. 最慢的两人c和d过河（时间：d）
4. b返回（时间：b） 总时间：2a + b + d

在实际应用中，我们需要每次比较这两种方案，选择时间更短的那个。以下是两种方案的对比表格：

1.3 特殊情况处理

除了主要的两种运输方案，我们还需要考虑一些特殊情况：

• 当剩余人数≤3时，可以直接采用特定策略：
  • 3人：a和c过河，a返回，a和b过河（时间：a+b+c）
  • 2人：直接一起过河（时间：b）
  • 1人：直接过河（时间：a）

这些边界情况在实际编程中容易被忽略，但往往是测试数据的重点考察对象。

2. C++代码实现详解

2.1 基础代码框架

让我们从最基本的代码结构开始。首先需要包含必要的头文件，并处理输入输出：

#include <iostream> #include <algorithm> using namespace std; const int MAX_N = 1005; int t[MAX_N]; // 存储每个人的过河时间 int main() { int T; // 测试用例数量 cin >> T; while (T--) { int n; // 当前测试用例的人数 cin >> n; for (int i = 0; i < n; ++i) { cin >> t[i]; } // 排序是贪心策略的前提 sort(t, t + n); // 计算总时间的逻辑将放在这里 cout << total_time << endl; } return 0; }

2.2 核心贪心算法实现

现在我们来填充核心的计算逻辑。根据前面的分析，我们需要从最慢的人开始处理，每次运送两人：

int total_time = 0; int i = n - 1; // 从最慢的人开始 while (i >= 3) { // 比较两种运输方案的时间 int plan1 = 2 * t[0] + t[i] + t[i-1]; int plan2 = t[0] + 2 * t[1] + t[i]; total_time += min(plan1, plan2); i -= 2; // 每次运送两人 } // 处理剩余人数≤3的情况 if (i == 2) { total_time += t[0] + t[1] + t[2]; } else if (i == 1) { total_time += t[1]; } else { // i == 0，只有一个人 total_time += t[0]; }

这段代码有几个关键点需要注意：

1. 必须先对数组进行排序，这是贪心策略成立的前提
2. 从数组末尾开始处理（最慢的人）
3. 每次循环处理两个人，所以索引i每次减2
4. 最后需要处理剩余1-3人的特殊情况

2.3 代码优化与注意事项

在实际竞赛中，我们还需要考虑一些优化和注意事项：

1. 输入输出效率：对于大规模数据，可以考虑使用更快的IO方式

   ios::sync_with_stdio(false); cin.tie(0);

2. 数组排序范围：注意sort函数的参数是半开区间

   sort(t, t + n); // 排序范围是[0, n)

3. 变量初始化：确保每次测试用例前相关变量被正确重置

   total_time = 0; // 必须在每个测试用例开始时重置

4. 边界条件检查：特别是n=1和n=2的情况需要单独处理

3. 测试数据生成与验证技巧

3.1 手动构造测试用例

为了验证我们的代码是否正确，需要设计各种类型的测试数据：

1. 极小规模测试：

   • 输入：1\n1\n 输出应为1
   • 输入：1\n2\n1 2\n 输出应为2

2. 典型测试用例：

   • 输入：1\n4\n1 2 5 10\n 输出应为17
   • 输入：1\n5\n1 3 6 8 12\n 输出应为29

3. 边界测试：

   • 最大人数测试：n=1000
   • 最大时间测试：所有人时间=100

3.2 自动化测试数据生成

对于大规模测试，我们可以编写随机数据生成器：

#include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main() { srand(time(0)); int T = rand() % 20 + 1; // 1-20组数据 cout << T << endl; for (int i = 0; i < T; ++i) { int n = rand() % 1000 + 1; // 1-1000人 cout << n << endl; for (int j = 0; j < n; ++j) { cout << rand() % 100 + 1 << " "; // 1-100秒 } cout << endl; } return 0; }

这个生成器可以产生符合题目要求范围的随机数据，帮助我们进行压力测试。

3.3 测试验证策略

验证程序正确性时，可以采用以下策略：

1. 对拍测试：将你的程序与一个已知正确的暴力解法（可能效率较低）进行比较
2. 极端值测试：专门测试n=1, n=2, n=1000等边界情况
3. 时间测试：确保程序在最大数据量时仍能在合理时间内完成

4. 竞赛实战技巧与常见陷阱

4.1 POJ与CSP-J题目差异

在实际竞赛中，不同平台对同一问题的描述可能有细微差别：

这些差异可能导致在某个平台AC的代码在另一个平台WA。因此，务必仔细阅读题目描述。

4.2 常见错误与调试技巧

在实现这个算法时，容易犯的错误包括：

1. 排序错误：忘记排序或排序范围不正确
2. 索引错误：在处理剩余人数时数组越界
3. 初始化问题：没有在每个测试用例前重置总时间
4. 整数溢出：虽然本题数据范围不大，但在其他问题中需要注意

调试时可以：

• 打印中间结果，观察每次运输的选择
• 对小规模数据手动计算验证
• 使用assert检查关键假设

4.3 性能优化建议

虽然本题的贪心解法已经是O(nlogn)复杂度（主要来自排序），但在其他问题中可能需要注意：

1. 使用更快的排序算法（如C++的sort通常足够）
2. 减少不必要的计算和变量拷贝
3. 使用更高效的数据结构（本题中简单数组即可）

5. 算法扩展与变种思考

5.1 问题变种与解法差异

"Crossing River"问题有多种变体，每种都可能需要不同的策略：

1. 船速恒定：不依赖人的速度，此时策略完全不同
2. 多人乘船：船容量>2时，贪心策略需要调整
3. 单程运输：不需要返回，问题简化为分批运输

5.2 相关竞赛题目推荐

为了加深理解，可以尝试以下类似题目：

• CSP-J2021初赛第15题
• POJ 1700 Crossing River
• UVa 10037 Bridge

这些题目虽然核心思想相似，但具体条件和约束可能不同，是很好的练习材料。

5.3 贪心算法的普适性思考

通过这道题，我们可以总结贪心算法的一些共性：

1. 局部最优选择：每次运输选择当前最优方案
2. 无后效性：当前选择不影响后续子问题的结构
3. 排序预处理：很多贪心算法都需要先对数据进行排序

理解这些特点有助于我们识别其他可以使用贪心算法解决的问题。