C++ - この問題、つまり村間に建設する基地局の最小数を解決する方法を知っている人はいますか?

Question

村間の距離を2Rで割るという考えは単純すぎる気がします

Answer 1

あなたの答えは間違いなく間違っています。簡単な例として、遠く離れた村が 2 つしかない場合、距離 /2R は非常に大きくなります。実際には、基地局は 2 つあれば十分です。
この質問は欲深いかもしれません。横軸で村を並べ替えると、その右側の R 距離以内に村を構築するのが最善です。 、できるだけ右側にあると、できるだけ多くの他の村をカバーできます)
このようにして、最初の基地局が構築され、いくつかの村をカバーし、残りの村に対して上記の操作を繰り返します。