ARC118 B Village of M People
最小値の最大化・最大値の最小化は二分探索. 今回は絶対値の最大値の最小化だが, 通常の場合と同様にして二分探索を適用してみよう. まず, 条件は式変形することで$ NB_i - MA_iの最大値の最小化に置き換えられる. そこで次の判定問題を考える. $ C(a) := $ NB_i - MA_iの最大値の最小値を$ a以下にできるか? とりあえず各村ごとに独立に考えてみる. 式変形することによって, $ B_iがとることができる範囲は$ \lceil \frac{MA_i - K}{N} \rceil \leq B_i \leq \lfloor \frac{MA_i + K}{N} \rfloorに定まる. $ aが各$ B_iがとりうる最小値(左端)の総和と最大値(右端)の総和の間に収まっていなければその$ aについてはダメであり, そうでないなら適切に処理することによって必ずちょうど$ aとすることができる. この判定問題には単調性があるため, この問題を$ O(M \log MN)で解くことができた.