搜索

首页  >  问答  >  正文

c++ - 谁知道这道题怎么解啊——村庄之间建设最少的基站数目?


感觉我自己想的太简单了,我的想法是村庄间的距离除以2R

世界只因有你世界只因有你2827 天前686

全部回复(1)我来回复

  • 迷茫

    迷茫2017-05-16 13:28:01

    你的答案肯定是不对的,一个简单的例子是只有两个村庄,隔着很远,那么距离/2R就会很大。其实两个基站就可以了。
    这题可以贪心,你把村庄按横坐标排序,你考虑最左边的村庄,他一定要被覆盖到,那么很显然,在他右边R的距离里建一个村庄是最好的(不仅覆盖了他,而且尽可能的往右,就能尽量多覆盖一些别的村庄)
    这么一来,第一个基站就建好了,他就覆盖掉了一些村庄,对剩下的村庄继续重复上述操作即可。

    回复
    0
  • 取消回复