題目描述
有 n 個人排隊向一個方向前進，他們前進的速度并不一定相同， 最開始即 t=0 時，每個人的位置并不相同，可以把他們放在數軸上，設他們前進的方向為正方向,對于從左往右第 i 個人,編號為 i，他的初始位置為xi ,初始速度為vi，編號為1的人（隊尾，位于數軸最左側）的位置總為坐標原點,即總有x1=0，(位置單位為米,速度單位為米每秒)， 雖然他們的前進速度不同，但是他們要保證前后順序不能變，即i追趕上 i+1 的時候, i 將會緊跟 i+1 以 i+1 的當前速度前進.可以認為他們是緊挨著的,之間的距離可以忽略不計， 求編號為1的人前進 s 米需要多少秒.
輸入
第一行兩個整數n,s,其中(1<=n,s<=100,000),代表n個人排隊前進,以及最后的一個人需要前進的距離為s米， 接下來n行,每行兩個整數xi,vi,代表第i個人的位置xi,以及他的初始速度vi,保證(0=x1≤x2≤…≤xn≤100,000,1≤vi≤100,000)，
輸出
輸出一個小數,按照四舍五入的原則恰好保留小數點后兩位（測驗資料保證答案的小數點后第三位不是4或5），
樣例輸入 Copy
3 4
0 3
1 2
2 1
樣例輸出 Copy
2.00
思路
第一種方法：按照最常見的思路方式，
- 第一步，查找相鄰兩個隊員之間相遇的最短時間，即全部遍歷一遍
- 第二步，在找到最短時間之后，進行每一位隊員的坐標的更新
- 第三步，根據被更新后的坐標，更新速度，即可，
- 第四步，回圈以上三個步驟即可（需要注意的是，在更新距離的時候，需要判斷x1是否到達s,進行相應的處理）
第二種方法：
- 第一步，從佇列的最后往前遍歷，直到某一位隊員的位置恰好小于等于s
- 第二步，計算與s坐標最近的隊員X(m)的耗時 tq，再次計算X(m-1)的耗時 th（需要注意的是，前面的隊員的速度不能夠超過后面的隊員的速度）
- 然后th = max{ th , tq}
- 重復2，3步驟，遍歷完一遍即可，
代碼決議
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179108.html
標籤：其他
上一篇：100個numpy問題8-100
下一篇：簡單數論總結（整除）