GESP 五级 · GESP 202409 C++ 五级 第 11 题

现在有 $n$ 个人要过河，每只船最多载2人，船的承重为 $100\,\text{kg}$。下列代码中，数组 weight 中保存有 $n$ 个人的体重（单位为 $\text{kg}$），已经按从小到大排好序，代码输出过河所需要的船的数目，采用的思想为（ ）。

int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
    if (weight[i] + weight[j] <= 100) {
        i++;
    }
    count++;
}
printf("过河的船数: %d\n", count);

仔细审题，明确已知条件和所求目标，运用相关知识点逐项分析。

审题时注意题目要求（选正确还是选错误），避免因审题不清失分。涉及代码的题目要逐行分析变量变化。

【考点】贪心算法｜双指针遍历

考纲定位：GESP 五级算法模块核心考点，命题人专门卡住"局部最优如何导向全局最优"的抽象理解——多数考生只会暴力枚举或死记结论，却看不懂贪心策略背后的数学直觉。

解题思维：代码本质是贪心——每次尝试最轻+最重能否同船（≤100kg），能则 i++（两人同船），否则 j--（最重单独）。循环 count++ 即每艘船。双指针 O(n) 遍历，比枚举所有配对 O(n²) 高效百倍。排序前提让贪心可行——若数组无序，局部最优无法保证全局最优。

陷阱拆解：A 枚举算法错在复杂度爆炸；C 迭代算法是循环统称，不体现策略；D 递归算法与代码无关。最阴险细节："已排序"是贪心成立的关键前提，若忽略，考生易误选枚举；边界处 i=j 时最后一人单独成船，count++ 仍会计入，体现贪心对尾部的处理。

反命题思维：若改成"每船 3 人"或"承重 80kg"，贪心需三指针或回溯；若去掉排序条件，贪心失效，应转向动态规划。刷到类似题，先问"命题人想考我什么？"——是贪心思想、双指针技巧，还是排序前提？