题解：Bridge over a rough river（湍急河流上的桥）

题目分析

本题要求计算一群人过桥的最短时间，限制条件为：

1. 每次最多两人同时过桥
2. 过桥需要手电筒，而只有一个手电筒
3. 两人同时过桥时，时间由较慢的人决定

核心问题在于如何安排过桥顺序，使得总时间最短。

算法思路

这是一个经典的过桥问题，关键在于处理最慢的两人时，有两种最优策略：

1. 策略1（快速往返）：

   • 最快的人带最慢的人过桥（时间=最慢的人）
   • 最快的人带次慢的人过桥（时间=次慢的人）
   • 总时间 = $2$*最快的人 + 最慢的人 + 次慢的人

2. 策略2（分组运输）：

   • 最快和次快的人先过桥（时间=次快的人）
   • 最快的人返回（时间=最快的人）
   • 最慢和次慢的人过桥（时间=最慢的人）
   • 次快的人返回（时间=次快的人）
   • 总时间 = 最快的人 + $2$*次快的人 + 最慢的人

每次迭代处理最慢的两人，选择两种策略中时间较短的，直到剩余人数不足$4$人时直接计算。

代码实现分析

#include <iostream>
#include <algorithm>
#include <cstdio>  // 添加头文件以声明scanf和printf
using namespace std;
int n;
int a[128];

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + n + 1);  // 按过桥时间升序排序
    int sum = 0;
    while(n > 0) {
        if(n == 1) {  // 只剩一人，直接过桥
            sum += a[1];
            break;
        }
        else if(n == 2) {  // 两人同时过桥，时间为较慢者
            sum += a[2];
            break;
        }
        else if(n == 3) {  // 三人过桥的最优解：最快带最慢，最快返回，再带次慢
            sum += a[1] + a[2] + a[3];
            break;
        }
        else {  // 处理四人及以上的情况，每次处理最慢的两人
            sum += min(2 * a[1] + a[n - 1] + a[n], a[1] + 2 * a[2] + a[n]);
            n -= 2;  // 每次处理后减少两人
        }
    }
    printf("%d\n", sum);
    return 0;
}