Download presentation
Presentation is loading. Please wait.
1
1753: Need for Speed ★★☆☆☆ 題組：Problem Set Archive with Online Judge
解題者：郭兆霖 解題日期：2019年4月5日 題意：Sheila的車的儀錶板壞了，所以顯示的時速與真正 的時速有一個誤差c(可能為負)，每筆測資第一行有路程n 段及總花費時間t，接著有n行輸入d(行駛距離)和s(儀錶 板顯示的速度)要你求出誤差c。
2
題意範例： Sample Input Sample Output / ( ) = 2 / ( ) = 4/3 / ( ) = 10/6 2 + 4/ /6 = 5 / ( ) = / ( ) = / ( ) = / ( ) = =10.0
3
解法： 這題沒有公式所以只能用binary search尋找，上界 最小要設定為 ，而下界則為輸入所給的速率當中 最小的乘上-1，這樣避免速率出現負數。 2 10 10 3 answer -1 上界 下界 平均 /(3+0)+10/(6+0)= 5 < 10 /(3-5)+10/(3-5)=-10 < 10 /(3-7.5)+10/(3-7.5) = < 10 /(3-8.25)+10/(3-8.25)= -3.2 < 10 最後平均為 -10 與答案不同
4
解法範例： 3 5 4 0 4 -1 10 3 以這筆測資，上界為 ，下界為1 (-1*-1)，平均 帶入c進行計算 4/( ) + 4/( ) + 10/( ) < 5(t) 求出來的值小於5(t)，代表除數太大，上界改為平均 繼續進行計算，最後得出答案 。
5
討論： 為何上界要設 ? 當n = 1000 t = 1 每行輸入 d = 1000 , s = -1000 為何下界要設最小值乘上負一? 假設正確答案為負100 第一次binary search 做完上界改為零下界 如果為 平均為 總和為負一 定小於所求t，上界變成 就無法找 到正確答案了
Similar presentations
