NOIP 普及组初赛 · NOIP 2010 普及组初赛试题 第 28 题

完善程序： (过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里，过桥时必须借助灯光来照明，很不幸的是，他们只有一盏灯。另外，独木桥上最多承受两个人同时经过，否则将会坍塌。每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 $n(2\leq n<100$ 和这 $n$ 个人单独过桥时需要的时间，请计算总共最少需要多少时间，他们才能全部到达河的左岸。

例如，有 $3$ 个人甲、乙、丙，他们单独过桥的时间分别为 $1,2,4$，则总共最少需要的时间为 $7$。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，总时间为 $2+1+4=7$。

#include <iostream>
using namespace std;

const int SIZE = 100;
const int INFINITY = 10000;
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;

int n, hour[SIZE];
bool pos[SIZE];

int max(int a, int b)
{
    if (a > b)
        return a;
    else
        return b;
}

int go(bool stage)
{
    int i, j, num, tmp, ans;
    if (stage == RIGHT_TO_LEFT) {
        num = 0;
        ans = 0;
        for (i = 1; i <= n; i++)
            if (pos[i

（本题为阅读程序 / 完善程序，完整题目与测试数据见平台）

这题考的是过河问题，核心是递归搜索+贪心策略。拿到题先想：右岸的人怎么分两组送过去？要么最快的人来回送灯，要么最快两人先过、送回来、最慢两人过、次快回来。代码里go(stage)就是干这个的，填空①判断右岸剩几人，②递归回左岸，③④⑤是枚举左岸送灯的人。

最容易错在①填num==1，其实右岸只剩1人时只能让他自己过，但题目默认n≥2且初始都在右岸，递归过程中右岸只剩1人意味着已经没人需要送了，直接返回当前ans即可，所以填num<=2或num<3更稳妥。另外④很多人只写hour[i]，忘了加上回右岸的时间，应该写hour[i]+go(RIGHT_TO_LEFT)。还有⑤漏写pos[i]=LEFT，导致状态没更新，后面枚举会出错。

考点与命题视角

这道题是经典的“过河问题”，属于贪心算法与递归/动态规划的结合。命题人喜欢挖两个坑：一是右岸只剩两人时直接一起过，二是左岸送灯的人不仅要算自己过桥的时间，还要加上回右岸的时间（很多人只填hour[i]）。代码里go(stage)函数用递归搜索，stage表示方向（RIGHT_TO_LEFT或LEFT_TO_RIGHT），pos数组记录每个人在哪边。

逐空推演

填空①：右岸只剩几人时直接返回

在go(RIGHT_TO_LEFT)里，先统计右岸人数num，并算出最慢的人的时间ans。如果右岸只剩1人，那这个人只能自己过，但题目隐含n≥2且初始都在右岸，递归过程中右岸只剩1人意味着已经没人需要送了（因为每次送两人过去，最多剩1人），直接返回ans即可。所以①填num<=2或num<3都行，表示右岸人数≤2时直接返回。

填空②：递归回左岸

接下来要枚举右岸两人一起过桥，把两人状态改为LEFT，计算时间max(hour[i],hour[j])，然后加上回右岸的时间。回右岸就是go(LEFT_TO_RIGHT)。所以②填go(LEFT_TO_RIGHT)。

填空③：左岸送灯的人

在go(LEFT_TO_RIGHT)里，要枚举左岸的人单独过桥送灯。pos[i]==LEFT表示i在左岸，所以③填pos[i]==LEFT或LEFT==pos[i]。

填空④：送灯总时间

i过桥到右岸的时间是hour[i]，然后要回左岸，回左岸的时间是go(RIGHT_TO_LEFT)。所以④填hour[i]+go(RIGHT_TO_LEFT)或go(RIGHT_TO_LEFT)+hour[i]。

填空⑤：更新状态

i过桥后状态变为RIGHT，但回左岸时状态要变回LEFT。所以⑤填pos[i]=LEFT。