AtCoder Regular Contest 075: D - Widespread

,

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

solution

答え$m$を二分探索。 $mB$回の爆風で死なない$h_i - mB \gt 0$な魔物に爆破の中心にしたときの増分$A-B$を追加で割り振っていって$m$回分で足りるかどうかを見る。 $O(N \log \max h_i)$。

implementation

にぶたんのテンプレ便利。

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
ll binsearch(ll l, ll r, function<bool (ll)> p) { // [l, r), p is monotone
    assert (l < r);
    -- l; -- r; // (l, r]
    while (l + 1 < r) {
        ll m = (l + r) / 2;
        (p(m) ? r : l) = m;
    }
    return r; // = min { x | p(x) }
}

int main() {
    int n, a, b; scanf("%d%d%d", &n, &a, &b);
    vector<int> h(n); repeat (i, n) scanf("%d", &h[i]);
    ll result = binsearch(0, *whole(max_element, h) + 1, [&](ll m) {
        ll cnt = 0;
        repeat (i, n) {
            ll x = h[i] - m * b;
            if (x >= 0) {
                cnt += (x + a-b-1) / (a-b);
            }
        }
        return cnt <= m;
    });
    printf("%lld\n", result);
    return 0;
}