Buses Between Cities

1qaz234Q · 2023-03-24 22:03:21 · 题解

题意简述

输入从 A 市出发的公交车的发车间隔时间 a 和到 B 市需要的时间 t_a，再输入从 B 市出发的公交车的发车间隔时间 b 和到 A 市需要的时间 t_b，最后输入 Simon 出发的时间，格式为 hh:mm。第一辆公交车早上 5:00 出发，最后一辆不迟于晚上 11:59 开出。求出 Simon 从 A 市到 B 市见到的公交车数量，不用计算他在起点和终点遇到的公交车。

题目分析

把 Simon 的出发时间转换为分钟，方便计算。早上 5:00 就是 300 分钟，晚上 11:59 就是 1439 分钟，晚上 12:00 就是 1440 分钟。

判断向 Simon 驶来的公交车中第一辆的出发时间是否为 5:00。如果是，那么向他驶来的第一辆公交车就是第一辆。否则计算是第几辆，向他驶来的第一辆公交车是第 \left\lfloor\dfrac{c-t_b-300}{b}\right\rfloor+2 辆。

然后计算他遇到的最后一辆公交车是第几辆，向他驶来的最后一辆公交车是第 \left\lceil\dfrac{\min(\min(c+t_a,1440),1439+t_b)}{b}\right\rceil 辆。\min(c+t_a,1440) 表示 Simon 到 B 市的时间。

最后计算 Simon 在路上遇到的公交车的数量。

时间复杂度为 O(1)。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,ta,b,tb,h,m;
    cin>>a>>ta>>b>>tb;
    scanf("%d:%d",&h,&m);
    int c=h*60+m;//把时间转换为分钟
    int d;//途中向 Simon 驶来的公交车中第一辆是第几辆
    if(c-tb<300){//如果途中向他驶来的公交车中第一辆出发时间是早上 5:00
        d=1;
    }
    else{
        d=(c-tb-300)/b+2;//计算他遇到的第一辆公交车是第几辆
    }
    int e=ceil(1.0*(min(min(c+ta,1440),1439+tb)-300)/b);//计算途中向他驶来的公交车中最后一辆是第几辆
    int ans=e-d+1;//计算 Simon 在路上遇到的公交车的数量
    cout<<ans;
}