여러 개의 양동이와 x개의 공이 주어졌다고 가정합니다. 볼을 양동이에 넣으면 그 안에 특별한 힘이 작용하여 두 볼 사이의 최소 힘을 최대화하는 방법을 찾아야 합니다. 위치 p와 q의 양동이에 있는 두 볼 사이의 힘은 |p - q|입니다. 우리에게 주어진 입력은 버킷 위치와 볼 x의 수를 포함하는 배열입니다. 우리는 그들 사이의 최소 힘을 찾아야 합니다.
따라서 입력이 pos =[2, 4, 6, 8, 10, 12], x =3과 같으면 출력은 4가 됩니다.
공은 12개의 버킷 배열에서 주어진 위치에 넣을 수 있습니다. 3개의 공은 위치 4, 8, 12에 넣을 수 있으며 그 사이의 힘은 4가 됩니다. 이 값은 더 이상 늘릴 수 없습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
ball_count() 함수를 정의합니다. 시간이 걸립니다
-
및 :=1
-
커 :=pos[0]
-
범위 1에서 n까지의 i에 대해 수행
-
pos[i] - curr>=d이면
-
ans :=ans + 1
-
커 :=pos[i]
-
-
-
반환
-
-
n :=위치의 크기
-
목록 위치 정렬
-
왼쪽 :=0
-
오른쪽 :=위치[-1] - 위치[0]
-
왼쪽 <오른쪽, 하는 동안
-
mid :=right - ((오른쪽 - 왼쪽) / 2)
의 하한값 -
ball_count(mid)>=x이면
-
왼쪽 :=중간
-
-
그렇지 않으면
-
오른쪽 :=중간 - 1
-
-
-
왼쪽으로 돌아가기
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(pos, x): n = len(pos) pos.sort() def ball_count(d): ans, curr = 1, pos[0] for i in range(1, n): if pos[i] - curr >= d: ans += 1 curr = pos[i] return ans left, right = 0, pos[-1] - pos[0] while left < right: mid = right - (right - left) // 2 if ball_count(mid) >= x: left = mid else: right = mid - 1 return left print(solve([2, 4, 6, 8, 10, 12], 3))
입력
[2, 4, 6, 8, 10, 12], 3
출력
4