c++ - Quelqu'un sait-il comment résoudre ce problème - le nombre minimum de stations de base à construire entre les villages ?

Question

J'ai l'impression que ma réflexion est trop simple. Mon idée est que la distance entre les villages est divisée par 2R

.

Answer 1

Votre réponse est définitivement fausse. Un exemple simple est qu’il n’y a que deux villages séparés par une longue distance, alors la distance /2R sera très grande. En fait, deux stations de base suffisent.
Cette question peut être gourmande. Vous triez les villages par l'abscisse. Si vous considérez le village le plus à gauche, il doit être couvert. Alors évidemment, il est préférable de construire un village à distance R à sa droite (non seulement il couvre He). , et le plus à droite possible, peut couvrir autant d'autres villages que possible)
De cette façon, la première station de base est construite, elle couvre certains villages, et continue de répéter les opérations ci-dessus pour les villages restants.