题解

思路

二分最终最小值 $x$。

做法

若 $A_i<x$，至少需要对它执行 $\left\lceil\frac{x-A_i}{a}\right\rceil$ 次增加；若 $A_i\ge x$，它最多能承受 $\left\lfloor\frac{A_i-x}{b}\right\rfloor$ 次减少而仍不低于 $x$。每次操作恰好使用一次增加和一次减少，因此当所有可提供的减少次数不少于所需增加次数时，$x$ 可行；反之任何操作方案都无法补足缺口。这个判定关于 $x$ 单调，故可在初始最小值到初始平均值之间二分最大可行值。

复杂度

判定一次需要 $O(N)$ 时间，二分次数为 $O(\log 10^9)$，总时间复杂度为 $O(N\log 10^9)$，空间复杂度为 $O(N)$；次数总和使用 64 位整数保存。