c++ - 誰知道這題怎麼解啊－村莊之間建造最少的基地台數目？

Question

感覺我自己想的太簡單了，我的想法是村莊間的距離除以2R

Answer 1

你的答案肯定是不對的，一個簡單的例子是只有兩個村莊，隔著很遠，那麼距離/2R就會很大。其實兩個基地台就可以了。
這題可以貪心，你把村莊按橫坐標排序，你考慮最左邊的村莊，他一定要被覆蓋到，那麼很顯然，在他右邊R的距離裡建一個村莊是最好的（不僅覆蓋了他，而且盡可能的往右，就能盡量多覆蓋一些別的村莊）
這麼一來，第一個基地台就建好了，他就覆蓋掉了一些村莊，對剩下的村莊繼續重複上述操作即可。