c++ - 이 문제(마을 사이에 건설해야 하는 최소 기지국 수)를 해결하는 방법을 아는 사람이 있습니까?

Question

제 생각은 너무 단순한 것 같아요. 마을 사이의 거리가 2R로 나누어져 있다는 생각이거든요

Answer 1

당신의 대답은 확실히 틀렸습니다. 간단한 예를 들면, 두 개의 마을만 멀리 떨어져 있고, 그러면 거리 /2R이 매우 클 것입니다. 실제로 두 개의 기지국이면 충분합니다.
이 질문은 욕심이 날 수 있습니다. 가장 왼쪽 마을을 고려하면 당연히 오른쪽 R 거리 내에 마을을 건설하는 것이 가장 좋습니다. 커버 그는, 그리고 가능한 한 오른쪽으로 최대한 많은 다른 마을을 커버할 수 있습니다)
이렇게 첫 번째 기지국이 건설되고, 일부 마을을 커버하고, 나머지 마을에 대해 위의 작업을 계속 반복합니다. 그것.