競技プログラミング用 知識集積所
ABC414D - Transmission Mission
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
「どこを範囲に入れるか」ではなく「どこを範囲に入れないか」と考えれば一瞬。
まず、家を座標順に一列に並べる。
基地局が1つなら、その左右端の距離が電波強度となる。
基地局2つの場合、どこか好きな1ヶ所、隣接する家の間を圏外にすることができる。
基地局3つの場合、どこか好きな2ヶ所、隣接する家の間を圏外にすることができる。
基地局が1つなら、その左右端の距離が電波強度となる。
基地局2つの場合、どこか好きな1ヶ所、隣接する家の間を圏外にすることができる。
基地局3つの場合、どこか好きな2ヶ所、隣接する家の間を圏外にすることができる。
基地局がＭ個ある場合は、どこか好きなM-1ヶ所、隣接する家の間を圏外にすることができる。
当然、それは貪欲法（未作成）で間隔が広いところから圏外にしていけばよい。
実装は、全ての隣り合う家の間隔を求め、ソートするなり、priority_queue（未作成）を使うなりで、どうとでもなる。
当然、それは貪欲法（未作成）で間隔が広いところから圏外にしていけばよい。
実装は、全ての隣り合う家の間隔を求め、ソートするなり、priority_queue（未作成）を使うなりで、どうとでもなる。
