HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth

題意：
給 N 個元素，問最小的 x ，使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] < x^N 為何。

制約：
1 ≤ N ≤ 1e5
1 ≤ A[ i ] ≤ 1e10

解法：
經典題，開 log 比較，二分搜 x。

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

import math
N = int( input() )
A = list( map( int, input().split() ) )
f = sum( math.log( A[ i ] ) for i in range( N ) )
lb, ub = 0, int( 1e10 )
ans = -1
while lb <= ub:
  mid = lb + ub >> 1
  x = math.log( mid ) * N
  if x > f:
    ans = mid
    ub = mid - 1
  else:
    lb = mid + 1
print( ans )