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