ARC144 B - Gift Tax (400)
$ a \gt bなら$ i,jを入れ替えて同じ操作を繰り返すと無限に大きくできるが制約からこれは起きない
ある$ A_iに対して$ a,bの療法の操作をすることはあり得ない
対向が同じならそもそも操作を消すことで両方の値を大きくできる
対向が異なるなら対向同士で操作をすることで$ A_iの操作を消して値を大きくできる
ある操作後の最小値を決めてそれを達成可能かどうかを二分探索する
それぞれの$ A_iについて
値が目標値未満なら目標値を超えるまで$ aを加え、操作回数を記録する
目標値より大きいなら目標値を下回らない範囲で$ bを引き、操作回数を記録する
$ aの操作回数が$ bの以下なら操作可能
ある要素についての操作回数は$ \mathcal{O}(1)で求まるので全体で$ \mathcal{O}(N \log \max A)