洛谷P1007题解析：过河问题的最短与最长时间计算（附代码）
1天前
一、题目解读
洛谷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函数简化计算，适合快速解题。进一步优化可考虑士兵分布特性，但原解法已满足题目要求。
原创内容 转载请注明出处
