（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸

第1题

（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥 走到河的左岸。 在这伸手不见五指的黑夜里， 过桥时必须借助灯光来照明， 很不幸的是，他 们只有一盏灯。 另外，独木桥上最多承受两个人同时经过，否则将会坍塌。 每个人单独过桥 都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 n（ 2≤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] == RIGHT) { 
                num++;   //人数加1
                if (hour[i] > ans) 
                    ans = hour[i];  //ans保留了最长的过桥时间，
            }
        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;  //pos是记录每个元素所处的位置。
    }
    cout<<go(RIGHT_TO_LEFT)<<endl;  //初始状态RIGHT_TO_LEFT
    return 0;
}