洛谷P1007题解析：过河问题的最短与最长时间计算（附代码）

一、题目解读

洛谷P1007题通常涉及一个经典的过河问题：给定桥的长度L和n个士兵的位置，士兵只能单向移动，且所有士兵的速度相同。题目要求计算所有士兵全部过桥所需的最短时间和最长时间。关键点在于士兵位置与桥两端距离的动态分析，需结合最值求解策略。

二、解题思路

采用“分情况讨论+最值更新”的策略：

1. 核心思想：士兵过桥的时间取决于其到两端（起点/终点）的最短距离或最长距离。

2. 计算逻辑：

○ 遍历每个士兵位置，分别计算到两端距离minDist和maxDist。

○ 最短时间：所有士兵中，选择“到两端最短距离”的最大值（即最慢的士兵决定minTime）。

○ 最长时间：同理，选择“到两端最长距离”的最大值（最远距离的士兵决定maxTime）。

3. 优化点：避免重复计算，直接通过比较pos与L-pos获取min/max距离，利用max函数动态更新最值。

三、解题步骤

1. 输入桥长L和士兵数量n。

2. 循环n次处理每个士兵：

○ 读入士兵位置pos。

○ 计算到两端距离：minDist = min(pos, L+1-pos)，maxDist = max(pos, L+1-pos)。

○ 更新最短时间：minTime = max(minTime, minDist)。

○ 更新最长时间：maxTime = max(maxTime, maxDist)。

3. 输出minTime和maxTime。

四、代码与注释

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

五、总结

该解法通过简洁的数学逻辑（距离比较+最值追踪）高效解决了过河问题。核心在于理解“最短/最长时间由最不利情况（最慢/最远士兵）决定”，避免了复杂模拟。代码利用min/max函数简化计算，适合快速解题。进一步优化可考虑士兵分布特性，但原解法已满足题目要求。