문제 링크
- http://icpc.me/2110
사용 알고리즘
- parametric search
시간복잡도
- O(N log 1e9)
풀이
좌표가 최대 10억까지 주어지므로 파라메트릭을 생각해봅시다.
공유기 사이의 거리를 m 이상으로 할 수 있는지는 O(N)만에 판단할 수 있습니다.
그렇다면 l을 0, r을 1e9로 설정해주고 이진 탐색을 하면 O(N log 1e9)만에 구할 수 있습니다.
거리를 m 이상으로 유지할 수 있는지 판단하는 함수는 그리디하게 구현하면 됩니다. 자세한 구현은 아래 코드를 참고해주세요.
전체 코드
1 |
|