bzoj#P2876. [Noi2012] 骑行川藏

[Noi2012] 骑行川藏

题目描述

蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨。川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地、同时合理分配好自己的体力是一件非常重要的事情。

由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响)。某一天他打算骑 nn​​ 段路,每一段内的路况可视为相同:对于第 ii​​ 段路,我们给出有关这段路况的三个参数 si,ki,vis_i , k_i , v_i'​​ ,其中 sis_i​​ 表示这段路的长度,kik_i​​ 表示这段路的风阻系数,viv_i'​​ 表示这段路上的风速(表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响)。若某一时刻在这段路上骑车速度为 vv​​,则他受到的风阻大小为 F=ki(vvi)2F = k_i ( v - v_i' )^2​(这样若在长度为 ss​​ 的路程内保持骑行速度 vv​​ 不变,则他消耗能量(做功)E=ki(vvi)2sE = k_i ( v - v_i' )^2 s​)。

设蛋蛋在这天开始时的体能值是 EuE_u​​ ,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 TT​​ 是多少。

必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式。

输入格式

第一行包含一个正整数 nn​​ 和一个实数 EuE_u​,分别表示路段的数量以及蛋蛋的体能值。

接下来 nn 行分别描述 nn 个路段,每行有三个实数 si,ki,vis_i , k_i , v_i',分别表示第 ii 段路的长度,风阻系数以及风速。

输出格式

输出一个实数 TT,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后 66​ 位。

本题没有部分分,你程序的输出只有和标准答案的差距不超过 10610^{-6}​ 时,才能获得该测试点的满分,否则不得分。

3 10000
10000 10 5
20000 15 8
50000 5 6
12531.34496464 

样例解释

一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为 5.12939919,8.03515481,6.178379675.12939919, 8.03515481, 6.17837967​。

数据规模与约定

对于 10%10\%​ 的数据,n=1n=1​;

对于 40%40\%​ 的数据,n2n\leq 2​;

对于 60%60\%​ 的数据,n100n\leq 100​;

对于 80%80\%​ 的数据,n103n\leq 10^3​;

对于 100%100\%​ 的数据,1n1041\leq n\leq 10^4​,0Eu1080\leq E_u\leq 10^80<si1050 < s_i\leq 10^50<ki10<k_i\leq1100<vi<100-100<v_i'<100​​​​。

数据保证最终的答案不会超过 10510^5