0w1

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 ) )