D. Widespread [AtCoder Beginner Contest 063 / AtCoder Regular Contest 075]

http://arc075.contest.atcoder.jp/tasks/arc075_b

解法

http://arc075.contest.atcoder.jp/submissions/1323651
二分探索で解く
「一回の爆発で中心の魔物はAダメージ,それ以外はBダメージ」を言い換える。
「一回の爆発で全体にBダメージ,1つの魔物に追加でA-Bダメージ」と考える。
こうすることで二分探索で解ける形になる。

関数check(x) := x回の攻撃で全員の魔物を倒せるか
まずx回攻撃しているので、それぞれの魔物はA*xダメージは負うことになる。
あとは、x回分追加でA-Bダメージをある魔物に食らわせることができるため、まだ生きている各魔物について、A-Bのダメージを何回与えるか数え上げる。
これが、x以下であれば、全員の魔物を倒せることになる。

これで二分探索すれば答え

typedef long long ll;
int N, A, B, H[101010];
//---------------------------------------------------------------------------------------------------
bool check(ll x) {
    ll c = 0;
    rep(i, 0, N) {
        ll h = 1LL * H[i] - 1LL * x * B;
        if (h <= 0) continue;
        c += h / A;
        if (h % A) c++;
    }
    return c <= x;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> A >> B;
    A -= B;
    rep(i, 0, N) cin >> H[i];
 
    int ng = 0, ok = 1010101010;
    while (ng + 1 != ok) {
        int x = (ng + ok) / 2;
        if (check(x)) ok = x;
        else ng = x;
    }
    cout << ok << endl;
}