c++ - Adakah sesiapa tahu bagaimana untuk menyelesaikan masalah ini - bilangan minimum stesen pangkalan yang akan dibina antara kampung?

Question

Saya rasa pemikiran saya terlalu mudah Idea saya ialah jarak antara kampung dibahagikan dengan 2R

Answer 1

Jawapan anda pasti salah Contoh mudah ialah hanya ada dua kampung yang dipisahkan dengan jarak yang jauh, maka jarak /2R akan menjadi sangat besar. Malah, dua stesen pangkalan sudah memadai.
Soalan ini boleh menjadi tamak Anda menyusun kampung mengikut abscissa Jika anda menganggap kampung paling kiri, ia mesti dilindungi Maka jelaslah, adalah yang terbaik untuk membina sebuah kampung dalam jarak R di sebelah kanannya tutup Dia, dan sejauh mungkin ke kanan, boleh meliputi sebanyak mungkin kampung lain)
Dengan cara ini, stesen pangkalan pertama dibina, dia meliputi beberapa kampung, dan terus mengulangi operasi di atas untuk kampung yang tinggal. ia.