CFR 780 B. The Meeting Place Cannot Be Changed ( Binary Search )
題意:
有些整數點上有朋友,每個朋友有個最高速率。問所有朋友集結到任意實數點需要的最短時間。
資料規模:
The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends.
The second line contains n integers x1, x2, ..., xn (1 ≤ xi ≤ 1e9) — the current coordinates of the friends, in meters.
The third line contains n integers v1, v2, ..., vn (1 ≤ vi ≤ 1e9) — the maximum speeds of the friends, in meters per second.
與正解的相對誤差 ≤ 1e-6
TL: 5000 ms
解法:
顯然以集和點作為參數,回傳最少時間的函數是凸函數,可以做三分搜。
但 Python 寫三分搜會 TLE。
可以直接二分搜,從中間切開比較 - EPS 和 + EPS 哪個好就往哪邊。
突然不能理解常數那麼大的三分搜存在的意義是什麼。
時間 / 空間複雜度:
O( N * 60 ) / O( N )
N = int( input() ) X = list( map( int, input().split() ) ) V = list( map( int, input().split() ) ) def calc( p ): # everyone is gathered to point p return max( abs( X[ i ] - p ) / V[ i ] for i in range( N ) ) lb, ub = 1.0, 1e9 while ub - lb > 5e-7: mid = ( lb + ub ) / 2 if calc( mid - 5e-7 ) < calc( mid + 5e-7 ): ub = mid else: lb = mid print( "%.9f" % calc( lb ) )