P1870 公交车

    • 10通过
    • 75提交
  • 题目提供者 JosephZheng
  • 评测方式 云端评测
  • 标签 模拟 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    某城市有个能容纳n辆公交车的停车场。每一天,这些公交车都要一辆一辆依次有序离开停车库去另一个终点站。这终点站距离停车场有d米的路程。当然第i辆公交车离开停车场的时间是ti秒,并以最大速度不超过vi米/秒行驶,加速度最大值为a。一辆公交车能瞬间减速,也能瞬间改变它的加速度。当然每辆车的最大加速度都一样为a。

    不管有多大的马力,一辆公交车都不能超过其他另外的公交车,如果一辆公交车追上另一辆公交车,那么后面追上的车跟前面被追的车一起并排行驶同时到达终点站。当然司机都是尽可能快的驾车到达终点站的。

    座位公交公司老板的你,希望每辆公交车都尽可能快的到达终点站。当然,公交车到达终点站时,速度可以没必要达到0。当一辆公交车离开停车场时,它的起始速度等于零。通过物理的观点解释的话,公交车可以看成是抽象的一个物体而已,除了能加速和减速,其他对速度的影响都可以忽略掉。

    输入输出格式

    输入格式:

    第一行三个空格隔开的整数n,a,d(1<=n<=10^5,1<=a,d<=10^6),分别表示公交车的数量,最大加速度。离终点站的距离。

    接下来n行,每行有一对整数ti,vi(0<=t1<t2…<tn-1<tn<=10^6,1<=vi<=10^6),分别表示每辆车离开停车场的时刻和能够行驶的最大速度。

    输出格式:

    输出每辆公交车到达终点站的时刻。一行表示一辆公交车的到达时刻,输出时刻的公交车顺序按照输入的公交车顺序。输出答案的相对或绝对误差不能超过10^(-4)(即截尾保留4位小数)。

    输入输出样例

    输入样例#1: 复制
    3 10 10000
    0 10
    5 11
    1000 1
    
    输出样例#1: 复制
    1000.5000
    1000.5000
    11000.0500
    

    说明

    【样例解释】

    第2辆公交车能追上第一辆公交车,在行驶到距离终点510.5公里处。然后还剩9489.5公里的路程,两辆车都以10公里/小时的速度,一起到达终点的,它们到达终点的时刻是1000.5秒,第三辆公交车不能赶上其他的公交车,他到达终点的时刻是11000.05秒。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。