c++ - Weiß jemand, wie man dieses Problem löst – die Mindestanzahl an Basisstationen, die zwischen Dörfern gebaut werden müssen?

Question

Ich habe das Gefühl, dass mein Denken zu einfach ist. Meine Idee ist, dass die Entfernung zwischen Dörfern durch 2R geteilt wird

迷茫 · Answer

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