题库 信息学奥赛题库 题目列表 完善程序:(过河问题) 在一个月黑风高的夜晚,有一群...
组合题

完善程序:

(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里,过桥时必须借助灯光来照明,很不幸的是,他们只有一盏灯。另外,独木桥上最多承受两个人同时经过,否则将会坍塌。每个人单独过桥都需要一定的时间,不同的人需要的时间可能不同。两个人一起过桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入 

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++;                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; }

第 1 题 填空
第 2 题 填空
第 3 题 填空
第 4 题 填空
第 5 题 填空
题目信息
2010年 初赛
-
正确率
0
评论
50
点击