[1] 答の存在について

はじめに，問題で問われている「操作後の \(\min(A_1, \ldots, A_N)\) としてありうる最大値」が存在することを確かめておきましょう．

\(a\leq b\) より，数列 \(A\) の総和は操作によって非増加です． したがって初期状態での \(A\) の総和を \(S\) とすると，操作結果において \(\min(A_1, \ldots, A_N) \leq S/N\) が成り立ちます．このことと，数列 \(A\) が常に整数列であることから，\(\min(A_1, \ldots, A_N)\) としてありうる最大値が存在することが分かります．

---

[2] 二分探索の利用

答を二分探索により求めることを考えます．そのためには，定数 \(C\) に対して次の判定問題を解くことができればよいです：

操作によって、\(\min(A_1, \ldots, A_N)\geq C\) を達成できるか否かを判定せよ．

\(\min(A_1, \ldots, A_N)\geq C\) という条件は，次のように項別の条件に書き変えることができて扱いやすいです．

操作によって、任意の \(i\) に対して\(A_i\geq C\) が成り立つようにできるか否かを判定せよ．

---

[3] 判定問題の解法

目的「任意の \(i\) に対して\(A_i\geq C\) 」を達成するための操作列について，次を仮定することができます：

• 同じ \(i\) に対して，\(+a\) する操作と \(-b\) する操作の両方は行わない．

実際，目的を達成する操作列について，

• \(A_i\) に \(+a\)，\(A_j\) に \(-b\) する操作
• \(A_i\) に \(-b\)，\(A_k\) に \(+a\) する操作

の両方が存在したとします．\(j = k\) ならばこれらの操作を取りやめる，\(j\neq k\) ならばこれらの操作を取りやめる代わりに「\(A_j\) に \(-b\)，\(A_k\) に \(+a\) する操作」を追加することで，目的を達成したまま操作回数を減らすことができます．したがって例えば目的を達成する操作列のうちで操作回数が最小のものをとれば，同じ \(i\) に対して，\(+a\) する操作と \(-b\) する操作の両方は行わないことが分かります．

すると，各 \(i\) に対して，次を満たす \(x_i\), \(y_i\) が計算できます：

• 初期状態において \(A_i < C\) であるような \(i\) について：\(+a\) 操作を \(x_i\) 回以上行う必要がある．\(-b\) 操作は行わない．
• 初期状態において \(A_i \geq C\) であるような \(i\) について：\(+a\) 操作は行わない．\(-b\) 操作は \(y_i\) 回まで行うことができる．

これを満たす操作列が存在することは，\(\sum x_i \leq \sum y_i\) と同値です．これで判定問題を解くことができます．

---

[4] まとめ

判定問題は，\(O(N)\) 時間で解くことができます．

二分探索の下界として，初期状態における \(\min A_i\) をとることができます．また [1] の議論により，二分探索の上界として初期状態における \(\sum A_i / N\) や \(\max A_i\) をとることができます．したがって本問題は \(O\bigl(N\log (\max A_i - \min A_i)\bigr)\) 時間で解くことができます．