GCJ 2017 R1B A. Steed 2: Cruise Control ( Binary Search )

Dashboard - Round 1B 2017 - Google Code Jam

嗯..? 好像根本就不用二分搜

題意：
T 筆測資。你在數線上的原點，目的地是 D。除了你現在騎著的馬，一共有 N 隻馬，任兩隻不共享位置的處於某整數位置，並有一個最高速度的屬性描述。當後面的馬追上前面的馬時，後面這隻馬會很有禮貌的做最低限度的減速，使得不會超過前面的馬。問你的馬最高時速可以是多少，以至於過程中不會減速。

制約：
1 ≤ T ≤ 100.
1 ≤ N ≤ 1000.
0 < Ki < D ≤ 1e9, for all i.
Ki ≠ Kj, for all i ≠ j. (No two horses start in the same position.)
1 ≤ Si ≤ 10000.

解法：
二分搜答案，獨立詢問是否會超過任一隻馬即可。

時間 / 空間複雜度：
O( N lg D )

T = int( input() )
for ti in range( 1, T + 1, 1 ):
  D, N = map( int, input().split() )
  K = []
  S = []
  for i in range( N ):
    k, s = map( int, input().split() )
    K.append( k )
    S.append( s )
  lb, ub = 0.0, 1e30
  for i in range( 200 ):
    mid = ( lb + ub ) / 2
    ng = False
    for i in range( 0, N ):
      if mid <= S[ i ]: continue
      if K[ i ] / ( mid - S[ i ] ) >= ( D - K[ i ] ) / S[ i ]: continue
      ng = True
      break
    if ng:
      ub = mid
    else:
      lb = mid
  print( "Case #%d: %.7f" % ( ti, lb ) )