当前位置:首页 > 洛谷 > 洛谷P1007题解析:过河问题的最短与最长时间计算(附代码)

洛谷P1007题解析:过河问题的最短与最长时间计算(附代码)

2个月前 (07-15)

洛谷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函数简化计算,适合快速解题。进一步优化可考虑士兵分布特性,但原解法已满足题目要求。

原创内容 转载请注明出处

分享给朋友:

相关文章

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

CSP-J方格取数题解|动态规划解法|洛谷P7074代码解析

一、题目解读题目要求在一个n×m的网格中,从左上角到右下角选择一条路径,路径上的数字可重复取用,求取数之和的最大值。路径限制为仅能向右或向下移动。需注意路径的灵活性与重复取数的可能性,传统单向动态规划...

NOIP 2008火柴棒等式题解(C++代码实现)  动态规划与枚举算法详解

NOIP 2008火柴棒等式题解(C++代码实现) 动态规划与枚举算法详解

一、题目解读火柴棒等式问题(NOIP 2008,洛谷P1149)要求使用给定数量的火柴棒,构造形如 A + B = C 的等式,其中A、B、C均为整数,且火柴棒总数恰好等于输入值。需统计符合条件的等式...

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

LeetCode 120题三角形最小路径和最优解法:动态规划详解与代码实现

一、题目解读LeetCode 120题“三角形最小路径和”要求给定一个由数字组成的三角形,从顶部开始向下移动,每次可向左或向右移动一格,计算从顶至底的最小路径和。三角形以二维向量形式给出,每层元素数量...

洛谷2789题解:直线交点数的递归求解与优化(附代码详解)

洛谷2789题解:直线交点数的递归求解与优化(附代码详解)

一、题目解读洛谷2789题要求计算n条直线在平面上两两相交时产生的不同交点数量。题目强调“不同”交点,需排除重复情况。解题关键在于如何高效枚举所有可能的交点组合,并避免重复计数。二、解题思路参考代码采...

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

力扣931题最小下降路径和解析 动态规划解法 LeetCode解题技巧

一、题目解读力扣931题「Minimum Falling Path Sum」(最小下降路径和)要求在一个n x n的整数矩阵中,计算从顶部到底部的最小路径和。路径只能从每个位置向下或对角线移动(即向下...

2022 CSP-J 上升点序(洛谷P8816)解题报告:动态规划求解最长上升序列

2022 CSP-J 上升点序(洛谷P8816)解题报告:动态规划求解最长上升序列

一、题目解读2022年CSP-J题目“上升点序”(洛谷P8816)要求给定一个平面点集,每个点的坐标(x,y)均为整数。题目需要构造一个最长的上升序列,序列中相邻点的坐标满足x和y均严格递增。允许使用...

发表评论

访客

看不清,换一张

◎欢迎参与讨论,请在这里发表您的看法和观点。