최소 거리 알고리즘

Question

나는 잠시 동안 여기에서 읽었지 만, 게시 한 것은 이번이 처음이므로이 태그가 올바르게 태그되지 않았 으면 사과드립니다. 어쨌든 나는 아래에서 설명하는 문제에 갇혀있다.

내 직업은 어떤 집과 가장 가까운 와이파이 라우터 사이의 최장 거리를 최소화하기 위해 n 와이파이 라우터를 정렬하는 것입니다. 저는 집이 1 차원 공간에 배열되어 있다고 가정 할 수 있습니다. 나는 초기 위치로부터 거리로서의 집 위치를 부여 받았고 위치는 정렬 된 순서로 주어졌다. 또한 O (m log L)에서이 문제를 해결해야합니다. 여기서 m은 주택 수이고 L은 주어진 최대 위치입니다.

나는 이것을 알아 내려고 노력했지만, 내가 생각해내는 알고리즘 중 어느 것도 복잡성에서 해결할 수 없다. 이 문제를 해결하는 방법에 대한 힌트를 주셔서 감사합니다.

Answer 1

여기에 힌트가 있습니다.

O(m) 거리에 상한값을 사용하는 함수를 쓰면 쉽고 라우터에서 그 집보다 위에있는 집이 없는지 확인하는 데 필요한 최소 라우터 수를 알 수 있습니다.

n 라우터를 사용하지 않는 가장 큰 거리를 검색하십시오.