NOIP 提高 2010 第一轮 第 31 题：完善程序（过河问题）第 4 空

题目

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

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

#include<iostream>
#include<cstring>
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]==RIGHT)
           {
               num++;
               if( hour[i]>ans)
                   ans=hour[i];
           }
        if(         ①        )
            return ans;
        ans=INFINITY;
        for(i=1;i<=n-1;i++)
           if(pos[i]==RIGHT)
               for(j=i+1;j<=n;j++)
                  if(pos[j]==RIGHT)
                  {
                      pos[i]=LEFT;
                      pos[j]=LEFT;
                      tmp=max(hour[i],hour[j])+         ②       ;
                      if(tmp<ans)
                         ans=tmp;
                      pos[i]=RIGHT;
                      pos[j]=RIGHT;

                  }
        return ans;
    }
    if(stage==LEFT_TO_RIGHT)
    {
        ans=INFINITY;
        for(i=1;i<=n;i++)
            if(         ③        )
            {
                pos[i]=RIGHT;
                tmp=        ④         ;
                if(tmp<ans)
                    ans=tmp;
                        ⑤      ;
            }
        return ans;
    }
    return 0;
}

int main()
{
    int i;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>hour[i];
        pos[i]=RIGHT;
    }
    cout<<go[RIGHT_TO_LEFT)<<endl;
    return 0;
}

④处应填（ ）

答案

hour[i]+go(RIGHT_TO_LEFT)

题解

考点定位

本题（过河第④空）考「回程总耗时」,对应大纲 4.2.3 递归（难度【3】）。

解题过程

返回者耗时 + 下一轮过桥递归：

``cpp tmp = hour[i] + go(RIGHT_TO_LEFT); ``

答案：hour[i]+go(RIGHT_TO_LEFT)。

易错提醒

① 单人回程耗时 hour[i]；② 递归回到右岸过桥阶段。