洛谷P1007题解：独木桥问题的最短和最长时间计算

一、问题描述

N个士兵在长度为L的独木桥上，每个士兵初始位置不同。士兵可以向左或向右移动，速度为1单位/秒。当两个士兵相遇时，他们会互相穿过对方。求所有士兵离开独木桥的最短和最长时间。

二、算法核心思想

1. 最短时间：所有士兵都选择离自己最近的桥端移动，取这些时间中的最大值

2. 最长时间：所有士兵都选择离自己最远的桥端移动，取这些时间中的最大值

三、完整代码实现（带详细注释）

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

int main() {
    int L, n;  // L:桥长度 n:士兵数量
    cin >> L >> n;
    
    int minTime = 0, maxTime = 0; // 初始化最短和最长时间
    
    for(int i = 0; i < n; i++) {
        int pos;  // 士兵位置
        cin >> pos;
        
        // 计算最短时间：选择离两端最近的距离的最大值
        int time = min(pos, L + 1 - pos); // 比较到左端和右端的距离
        minTime = max(minTime, time); // 更新最短时间
        
        // 计算最长时间：选择离两端最远的距离的最大值
        time = max(pos, L + 1 - pos); // 比较到左端和右端的距离
        maxTime = max(maxTime, time); // 更新时间
    }
    
    cout << minTime << " " << maxTime << endl;
    return 0;
}

四、算法分步解析

1. 输入处理：

• 读取桥长度L和士兵数量n

• 初始化minTime和maxTime为0

2. 遍历处理每个士兵：

• 读取每个士兵的位置pos

• 计算该士兵到桥两端的距离

• 最短时间：取min(左端距离,右端距离)的最大值

• 最长时间：取max(左端距离,右端距离)的最大值

3. 输出结果：

• 打印最短时间和最长时间

五、常见误区与调试技巧

1. 忘记初始化minTime和maxTime

2. 桥长度计算错误（注意L+1）

3. 混淆最短和最长时间的计算逻辑

4. 输入输出格式错误

六、扩展思考

1. 如果士兵速度不同如何解决？

2. 如果桥有多个出口如何计算？

3. 如何统计所有士兵的移动方向？

4. 如果考虑士兵体积会怎样影响结果？