def min_crossing_time(n, times):
    """
    计算N个人过桥的最短时间
    
    Args:
        n: int - 人数
        times: List[int] - 每个人的过桥时间
    
    Returns:
        int - 最短总时间
    """
    if n == 1:
        return times[0]
    elif n == 2:
        return max(times[0], times[1])
    elif n == 3:
        return times[0] + times[1] + times[2]
    
    # 排序，确保 times[0] <= times[1] <= ... <= times[n-1]
    times.sort()
    
    total_time = 0
    remaining = n
    
    # 处理人数大于3的情况
    while remaining > 3:
        # 策略1: 最快的带最慢的，最快的回来，最快的带次慢的，最快的回来
        strategy1 = 2 * times[0] + times[remaining - 1] + times[remaining - 2]
        
        # 策略2: 最快和次快过去，最快回来，最慢和次慢过去，次快回来
        strategy2 = times[0] + 2 * times[1] + times[remaining - 1]
        
        # 选择时间较少的策略
        total_time += min(strategy1, strategy2)
        remaining -= 2  # 最慢的两个人已经过桥了
    
    # 处理剩余的特殊情况
    if remaining == 3:
        total_time += times[0] + times[1] + times[2]
    elif remaining == 2:
        total_time += times[1]  # 两人一起过
    else:  # remaining == 1
        total_time += times[0]
    
    return total_time

# 主程序
if __name__ == "__main__":
    n = int(input().strip())
    times = list(map(int, input().strip().split()))
    
    result = min_crossing_time(n, times)
    print(result)

算法执行过程示例

以输入 [1, 2, 5, 10] 为例：

排序后：[1, 2, 5, 10]
剩余4人 > 3，计算两种策略：
- 策略1：2*1 + 10 + 5 = 17
- 策略2：1 + 2*2 + 10 = 15
- 选择策略2（15）
执行策略2的具体步骤：
- 1和2过去（时间2）
- 1回来（时间1）
- 5和10过去（时间10）
- 2回来（时间2）
- 累计时间：2+1+10+2 = 15
剩余2人（1和2），一起过去（时间2）
总时间：15 + 2 = 17

注意：这里有个细节，我们的算法计算的是将最慢两人送过去的代价，但实际上策略2的完整执行还包括最后两人过桥的时间。

让我重新验证一下：

实际上对于4个人的情况，最优方案是：

1和2过去 → 时间2
1回来 → 时间1
5和10过去 → 时间10
2回来 → 时间2
1和2过去 → 时间2 总时间：2+1+10+2+2 = 17

而我们的算法中，当remaining=4时选择策略2（代价15），然后remaining=2时加上times[1]=2，总共17，是正确的。

这个贪心算法通过每次最优地处理最慢的两个人，确保了全局最优解。

注意事项与题目启发

需要注意的问题

1. 边界条件的完整性

if n == 1:
    return times[0]
elif n == 2:
    return max(times[0], times[1])
elif n == 3:
    return times[0] + times[1] + times[2]

n=1：只有一个人，直接过桥
n=2：两人一起过，取较慢者时间
n=3：必须让最快的来回接送，固定模式
容易遗漏n=3的特殊情况，错误地套用通用策略

2. 策略计算的准确性

策略1公式：2*a[0] + a[n-1] + a[n-2]
- 对应：快带慢→快回→快带次慢→快回
策略2公式：a[0] + 2*a[1] + a[n-1]
- 对应：快和次快→快回→慢和次慢→次快回
常见错误：混淆两个策略的公式，或者忘记最后还需要处理剩余人员

3. 排序的重要性

必须先对时间数组排序，否则无法正确应用贪心策略
排序后才能保证times[0]是最小值，times[1]是次小值

4. 循环终止条件

循环条件是remaining > 3，不是remaining > 2
当剩余3人时，需要特殊处理，不能继续应用通用策略
错误的终止条件会导致无限循环或错误结果

5. 算法逻辑的理解误区

不是简单的"总是用最快的人接送"：有时用次快的人配合更优
策略选择依赖具体数值：需要比较两种策略的实际代价
最后一步的处理：循环结束后还要处理剩余的1-3人

6. 输入数据的假设

题目保证时间都是正整数，但实际编码中应考虑输入验证
人数范围1-1000，时间范围1-100，不会出现溢出问题

7. 测试用例覆盖

需要测试多种情况：

极端情况：[1, 100]、[1, 2, 100, 100]
相同时间：[5, 5, 5, 5]
递增序列：[1, 2, 3, 4, 5]
大差异：[1, 2, 50, 100]

题目的启发

1. 贪心算法的复杂性

多策略选择：不是单一的贪心规则，而是比较多个策略的代价
局部最优≠直观最优：最快的人不一定总是最优的"搬运工"
数学分析的重要性：需要通过公式推导来比较不同策略

2. 问题分解的思维方式

逆向思维：从最困难的部分（最慢的人）开始解决
分治思想：将大问题分解为"处理最慢两人 + 剩余问题"
模式识别：识别出重复的子问题结构

3. 算法设计的经典模式

这个问题展示了经典的"两难选择"模式：

每次面临多个可行方案
需要通过数学比较选择最优
选择后问题规模减小，但性质不变

4. 实际应用价值

资源调度：类似的问题出现在任务调度、资源分配中
成本优化：在多个约束条件下寻找最小成本方案
决策制定：现实中的很多决策都需要在不同策略间权衡

5. 编程思维的培养

从具体到抽象：通过具体例子总结出通用规律
边界思维：特别关注特殊情况的处理
验证驱动：通过手动模拟验证算法正确性

6. 算法复杂度的权衡

预处理代价：O(n log n)排序 vs O(n)处理
空间效率：原地排序，空间复杂度O(1)
时间效率：线性处理，整体效率很高

7. 扩展思考方向

这个问题可以引申出更多变种：

多人手电筒：如果有k个手电筒怎么办？
桥容量变化：桥能容纳k人同时过
动态时间：过桥时间随次数变化
返回约束：某些人不能单独返回

8. 面试价值

经典程度：这是算法面试中的经典贪心问题
考察维度：
- 逻辑分析能力
- 数学建模能力
- 边界处理能力
- 代码实现能力
延伸性强：可以自然过渡到其他贪心或动态规划问题

9. 学习方法论

理解本质：不要死记硬背策略公式，要理解为什么这样选择
手动验证：通过小例子手动模拟算法执行过程
举一反三：将这种多策略比较的思路应用到其他问题

这个题目完美展示了贪心算法的精髓：在看似复杂的约束条件下，通过深入分析找到简洁而高效的解决方案。它告诉我们，最优策略往往不是最直观的那个，而是需要通过严谨的数学分析得出的。