import random
import math
N,J,H=100000, 100, 1000000
#N,J,H = 18, 4, 100
arr = list(sorted([random.randint(1,H) for i in range(0,N)]))
#arr = [8, 16, 22, 26, 29, 32, 39, 50, 51, 54, 56, 59, 60, 64, 64, 65, 71, 77]
def canJump(arr, N, S):
steps, start = 0, 0
print("S:",S)
for i in range(1,N):
if (i-start <= S and arr[i]-arr[start] <= S):
continue
else: #Exceed the strength, we can only go to the previous element, so start = i-1
steps += 1
start = i-1
if (steps == J and start < N - 1): # if steps == J, but we still don't reach the end
print(S, "is not OK at ", i)
return False
return True
def jumper(arr, N, J):
maxDiff = max([arr[i]-arr[i-1] for i in range(1,N)])
start, end = max(maxDiff, math.ceil(N/J)), N
print("start,end:",start, end)
while (start < end):
mid = start + (end - start) // 2
if (canJump(arr, N, mid)):
end = mid
else:
start = mid+1
return start
print("result:",jumper(arr, N, J))
import random
import math
#N,J,H=100000, 100, 1000000
N,J,H = 18, 4, 100
#arr = list(sorted([random.randint(1,H) for i in range(0,N)]))
arr = [8, 16, 22, 26, 29, 32, 39, 50, 51, 54, 56, 59, 60, 64, 64, 65, 71, 77]
def canJump(arr, N, S):
steps, start = 0, 0
#print("S:",S)
for i in range(1,N):
if (i-start <= S and arr[i]-arr[start] <= S):
continue
else: #Exceed the strength, we can only go to the previous element, so start = i-1
steps += 1
start = i-1
if (steps == J and start < N - 1): # if steps == J, but we still don't reach the end
#print(S, "is not OK at ", i)
return False
return True
def jumper(arr, N, J):
maxDiff = max([arr[i]-arr[i-1] for i in range(1,N)])
start, end = max(maxDiff, math.ceil(N/J)), max(N, H)
print("start,end:",start, end)
while (start < end):
mid = start + (end - start) // 2
if (canJump(arr, N, mid)):
end = mid
else:
start = mid+1
return start
print("result:",jumper(arr, N, J))