题目来源

CCF NOIP 2010 初赛，普及组 C++，第四部分“完善程序”第 2 题。

题目描述

在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在伸手不见五指的黑夜里，过桥时必须借助灯光照明，但他们只有一盏灯。独木桥上最多承受两个人同时经过，否则将会坍塌。

每个人单独过桥都需要一定的时间，不同的人需要的时间可能不同。两个人一起过桥时，由于只有一盏灯，所以所需时间等于较慢的那个人单独过桥所花的时间。

现输入 n（2 <= n < 100）和这 n 个人单独过桥所需的时间，请计算他们全部到达河的左岸所需的最少总时间。

例如，3 个人甲、乙、丙单独过桥的时间分别为 1、2、4。甲、乙一起过桥，甲返回送灯，甲、丙再一起过桥，总时间为 2 + 1 + 4 = 7。

请阅读下面的递归程序并填写空 1 至空 5。

作答要求

• 每个输入框只填写对应空缺处的内容，不填写空号。
• 不要额外填写题目中已经给出的分号、括号或其他符号。
• 系统已收录参考答案中明确给出的常见等价写法、布尔常量替换及常见空格形式；仍建议按规范 C++ 写法作答。
• 原卷中五空每空 3 分。本题作为独立练习题，五空各 20 分，共 100 分。

程序

#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++;
                if (hour[i] > ans)
                    ans = hour[i];
            }

        if (/* 空 1 */)
            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]) + /* 空 2 */;
                        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 (/* 空 3 */) {
                pos[i] = RIGHT;
                tmp = /* 空 4 */;
                if (tmp < ans)
                    ans = tmp;
                /* 空 5 */;
            }
        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;
}

作答区

空 1（20 分）： {{ input(1) }}

空 2（20 分）： {{ input(2) }}

空 3（20 分）： {{ input(3) }}

空 4（20 分）： {{ input(4) }}

空 5（20 分）： {{ input(5) }}