ARC118 B - Village of M People (400)
可能な最小の差分を二分探索で求める
あり得る最大値は$ \max(n^2,m^2)
判定は以下のように行う
k個それぞれについて$ M人にしたときに設定した最大の差以下になるような取り得る値の下限と上限を求める
作れない場合は判定全体を終わらせる
下限と上限でそれぞれ和を持っておいて足す
人数の下限と上限の間に$ Mが来れば作れることが分かる
構成は以下の様に行う
下限上限まで同じように行う
全グループ下限にしたときの余りの人数を求める
好きな順で各グループに上限までの差と余りの小さい方を足す
下限から上限の間なら何人でも条件を満たしているため
ここまでやってもなぜかWA
小数をlong doubleで扱うことでAC
一回の判定が$ \mathcal{O}(K)、全体で$ \mathcal{O}(K \log \max(n,m))