ARC144B - Gift Tax

考え方

最小値の最大値なので，二分探索を考える．

すべての要素を$x$以上にできるかは，

• $x + b$以上の要素から$b$減らせる操作回数
• $x$未満の要素から$a$増やさなければならない操作回数

の2つを比較することで判定できる．

回答例

N, a, b = map(int, input().split())
A = list(map(int, input().split()))

def f(x):
    neg, pos = 0, 0
    for AA in A:
        if AA < x:
            neg += (x - AA + a - 1) // a
        if AA - b >= x:
            pos += (AA - x) // b
    if pos >= neg:
        return True
    return False

ok = min(A)
ng = 10 ** 10
while ng - ok > 1:
    mid = (ok + ng) // 2
    if f(mid):
        ok = mid
    else:
        ng = mid
print(ok)