骑行川藏(noi2012)
【题目描述】
蛋蛋非常热衷于挑战自我,今年暑假他准备沿川藏线骑着自行车从成都前往拉萨.
川藏线的沿途有着非常美丽的风景,但在这一路上也有着很多的艰难险阻,路况变化多端,而蛋蛋的体力十分有限,因此在每天的骑行前设定好目的地,同时合理分配好自己的体力是一件非常重要的事情.
由于蛋蛋装备了一辆非常好的自行车,因此在骑行过程中可以认为他仅在克服风阻做功(不受自行车本身摩擦力以及自行车与地面的摩擦力影响).
某一天他打算骑 nn 段路,每一段内的路况可视为相同:对于第 ii 段路,我们给出有关这段路况的 3 个参数 si,ki,vi',其中 si表示这段路的长度, ki表示这段路的风阻系数, vi' 表示这段路上的风速( 表示在这段路上他遇到了顺风,反之则意味着他将受逆风影响).若某一时刻在这段路上骑车速度为 vv ,则他受到的风阻 大小为 F=ki*(v-vi')^2(这样若在长度为 ss 的路程内保持骑行速度 v 不变,则他消耗能量(做功) E=ki*(v-vi')^2*s
设蛋蛋在这天开始时的体能值是 Eu ,请帮助他设计一种行车方案,使他在有限的体力内用最短的时间到达目的地。请告诉他最短的时间 T 是多少.
输入输出格式
输入格式:
第一行包含一个正整数 N和一个实数 Eu ,分别表示路段的数量以及蛋蛋的体能值.
接下来 N 行分别描述 N个路段,每行有 3 个实数 si,ki,vi'分别表示第 i 段路的长度,风阻系数以及风速.
【输出格式】:
输出一个实数 T ,表示蛋蛋到达目的地消耗的最短时间,要求至少保留到小数点后 6 位.
【输入样例#1】:
3 10000
10000 10 5
20000 15 8
50000 5 6
【输出样例#1】:
12531.34496464
说明
样例说明
一种可能的方案是:蛋蛋在三段路上都采用匀速骑行的方式,其速度依次为 5.12939919,8.03515481,6.178379675.12939919,8.03515481,6.17837967 .
评分方法
本题没有部分分,你程序的输出只有和标准答案的差距不超过 10^(-6)时,才能获得该测试点的满分,否则不得分.
数据规模与约定
对于 10% 的数据, N=1 ;
对于 40% 的数据, N≤2 ;
对于 60% 的数据, N≤100 ;
对于 80% 的数据, N≤1000 ;
对于 100% 的数据, N≤10^4,0≤Eu≤10^8,0≤si≤100 000,-100<vi'<100
数据保证最终的答案不会超过 10^5
【提示】
必然存在一种最优的体力方案满足:蛋蛋在每段路上都采用匀速骑行的方式.
信息
- 难度
- 10
- 分类
- (无)
- 标签
- 递交数
- 3
- 已通过
- 0
- 通过率
- 0%
- 上传者