给出每个office的距离,以及需要再hour时间内依次去到所有office,去每个office的时间是dis[i]/hour向上取整,二分,注意r要开大点,以及一开始要特判无论多块都无法按时arrive的情况
#852
#Runtime: 2487 ms (Beats 90.91%)
#Memory: 25 MB (Beats 72.73%)
class Solution(object):
def minSpeedOnTime(self, dist, hour):
"""
:type dist: List[int]
:type hour: float
:rtype: int
"""
eps = 1e-6
l, r = 1, 1000000000
if hour <= len(dist) - 1:
return -1
while l < r:
mid = (l + r) // 2
t = 0
for x in dist[:-1]:
t += x // mid
if x % mid:
t += 1
t += 1.0 * dist[-1] / mid
if t <= hour:
r = mid
else:
l = mid + 1
return l