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

问题描述

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

问题解答

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