笨鸟先飞的同时也要追上别人的脚步 审核通过

一、题目解释

需要骑行 米从起点到终点，但他有一个习惯：他必须与其他人以相同的速度骑行。当遇到速度更快的人时，他会立即跟随这个人的速度并一起骑行到终点。

题目要求计算 以这种方式骑行到终点所需的最短时间，并向上取整。

二、问题分解

1. 关键条件：

• 只有在遇到速度更快的人时才会改变速度，并且会跟随这个人的速度到终点。

• 如果某人的速度比 当前速度快且他比 晚出发，那么 会被追上并跟随他骑行。

2.基本假设与推论：

• 所有速度比 慢或同时出发的骑行者对 的到达时间没有影响，因为他们无法追上或超越 。

• 因此，只有那些速度更快且出发时间晚于或等于 的骑行者，才可能影响到 的骑行时间。

3.贪心策略：

• 为了最小化到达终点的时间， 应该尽可能早地与第一个比他速度快的骑行者汇合。

• 一旦找到符合条件的骑行者，我们计算 在该骑行者速度下到达终点所需的时间。

• 最终的结果应该是这些可能时间中的最小值。

三、算法选择与优化

基于上述分析，我们可以采用贪心算法：

1. 初始化：

• 使用一个足够大的值作为初始时间（例如 ），这个值在程序中通常用作“无穷大”的代替，用来初始化最小时间，以便后续更新。

• 的优势： 是一个常用的大整数常量，在代码中用作“无穷大”值，它比 （即 ）要小，所以在进行加

法运算时不会导致整数溢出，是一种安全的初始化方式。

2. 逐步优化：

• 遍历每一个骑行者的速度和出发时间，如果该骑行者速度更快且出发时间不早于 ，则计算 在该骑行者速度下到达终点的时间。

• 比较并更新最短时间。

3. 计算到达时间：

• 题目中速度以 公里 小时 为单位，而距离为 米，因此需要将速度转换为 米 秒。通过公式 进行转换，以确保计算的正确性。

• 对于每个符合条件的骑行者，计算 从该骑行者出发时间开始到达终点的时间：

• 其中， 是骑行速度， 是出发时间。公式中 为距离（米）， 单位为 公里 小时， 为秒数，将速度单位转换为 米 秒。

4. 选择最优解：

• 输出这些时间中的最小值，作为 最快到达终点的时间。

四、代码实现

#include <iostream>
using namespace std;
#include <math.h>
#define MIN 0x3f3f3f3f

int main()
{
    int n, t, time, min;
    double v;
    
    while (cin >> n && n) // 读取骑行者数量，当为0时结束
    {
        min = MIN; // 使用一个很大的初始值
        
        for (int i = 1; i <= n; i++)
        {
            cin >> v >> t; // 读取速度和出发时间
            
            if (t >= 0) // 如果出发时间非负，表示可以追上
            {
                // 计算该骑行者带领 Charley 到终点的总时间
                time = (int)(t + ceil(4500 / (1000.0 * v / 3600)));  
                
                if (time < min)
                    min = time; // 记录最小的到达时间
            }
        }
        
        cout << min << endl; // 输出最短时间
    }
    
    return 0;
}

五、总结

1. 贪心策略的合理性：

• 通过分析发现， 的最短到达时间完全取决于他能跟随的最早速度更快的骑行者。因此，采用贪心策略是合理的，即每次只考虑最早遇到的能够提升速度

的骑行者。