解题思路

N 个人夜里过桥，只有一只手电筒，桥一次最多走两个人，两人一起走的时间按慢的那个算。问最短过桥时间。

这是经典的贪心问题。核心思路：让最慢的两个人尽量一起过桥，减少他们单独在桥上的次数。

先把所有人按时间从小到大排序，a[0] 最快，a[n-1] 最慢。

每次把最慢的两个人（a[n-2] 和 a[n-1]）送过去，有两种方案：

方案一：最快的两人来回送

1. a[0] 和 a[1] 先过（用时 a[1]）
2. a[0] 送手电筒回来（用时 a[0]）
3. a[n-2] 和 a[n-1] 一起过（用时 a[n-1]）
4. a[1] 回来接 a[0]（用时 a[1]） 总时间 = a[0] + 2×a[1] + a[n-1]

方案二：最快的人分别带两个最慢的过

1. a[0] 带 a[n-1] 过（用时 a[n-1]）
2. a[0] 回来（用时 a[0]）
3. a[0] 带 a[n-2] 过（用时 a[n-2]）
4. a[0] 回来（用时 a[0]） 总时间 = 2×a[0] + a[n-2] + a[n-1]

两个方案取用时少的那个，然后这最慢的两个人就过去了，n 减 2，继续处理剩下的人。

最后收尾：

• 剩 1 人：加 a[0]
• 剩 2 人：加 a[1]
• 剩 3 人：a[0] 带 a[2] 过，a[0] 回，a[0] 带 a[1] 过，总 a[0]+a[1]+a[2]

举个例子：1 2 5 10

• 方案一 = 1 + 2×2 + 10 = 15
• 方案二 = 2×1 + 5 + 10 = 17
• 取 15，剩 2 人（1 和 2），再加 2 → 17 ✅

参考代码

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int n, a[1000];
    while (scanf("%d", &n) != EOF) {
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - 1 - i; j++) {
                if (a[j] > a[j + 1]) {
                    int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
                }
            }
        }

        int ans = 0;
        while (n > 3) {
            int t1 = a[0] + 2 * a[1] + a[n - 1];
            int t2 = 2 * a[0] + a[n - 2] + a[n - 1];
            ans += (t1 < t2 ? t1 : t2);
            n -= 2;
        }
        if (n == 1) ans += a[0];
        else if (n == 2) ans += a[1];
        else ans += a[0] + a[1] + a[2];

        printf("%d\n", ans);
    }
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，冒泡排序
• 空间复杂度：O(N)，一个数组存时间