Subscribed unsubscribe Subscribe Subscribe

0w1

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 )