숫자 배열 A가 있다고 가정하고 A에서 i 번째 숫자는 섬이 있는 위치이고 또 다른 정수 k가 제공됩니다(1 ≤ k
따라서 입력이 A =[7, 20, 41, 48], k =2와 같은 경우 출력은 28이 됩니다. 마지막 섬 7에서 20에서 48에 도달하는 두 가지 방법이 있으므로 여기에서 최대 거리 연속된 두 섬 사이의 거리는 48에서 20 사이, 즉 28입니다. 여기에서 7에서 41에서 48까지 연속된 두 섬 사이의 최대 거리는 41에서 7, 즉 34입니다. 따라서 28과 34의 최소값은 28입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
isPossible() 함수를 정의합니다. arr,dist,k
n :=arr의 크기
요구:=0
현재 :=0
이전 :=0
0에서 n 사이의 i에 대해 수행
현재는 n과 같지 않으며 (arr[current] - arr[이전]) <=dist, do
현재 :=현재 + 1
요구 사항 :=요구 사항 + 1
전류가 n과 같으면
루프에서 나오다
이전 :=현재 - 1
전류가 n과 같지 않으면
거짓을 반환
req <=k이면
참을 반환
거짓을 반환
기본 방법에서 다음을 수행하십시오 -
n :=arr의 크기
왼쪽 :=0
right :=arr의 마지막 요소
답변 :=0
동안 왼쪽 -=오른쪽, 수행
중간 :=(왼쪽 + 오른쪽) / 2;
isPossible(arr, mid, k)이 0이 아니면
as :=중간
오른쪽 :=중간 - 1
그렇지 않으면
왼쪽 :=중간 + 1
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def isPossible(arr,dist, k) :
n = len(arr)
req = 0
current = 0
previous = 0
for i in range(0, n):
while (current != n and (arr[current] - arr[previous]) <= dist):
current += 1
req += 1
if (current == n):
break
previous = current - 1
if (current != n):
return False
if (req <= k):
return True
return False
def minimum_distance(arr, k):
n = len(arr)
left = 0
right = arr[-1]
ans = 0
while (left <= right):
mid = (left + right) // 2;
if (isPossible(arr, mid, k)):
ans = mid
right = mid - 1
else:
left = mid + 1
return ans
arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))
입력
[7, 20, 41, 48] , 2
출력
28
