Gluttony [AtCoder Beginner Contest 144 E]

https://atcoder.jp/contests/abc144/tasks/abc144_e

前提知識

• 二分探索

解説

https://atcoder.jp/contests/abc144/submissions/8164566

まず、最大値の最小化ということで二分探索かというところ。
最大値が決まっていれば、各メンバーについて何回修行が必要かわかれば良さそう。
ここで、エスパーをする必要がある。
Aを昇順ソート、Fを降順ソートして、A[i]F[i]とマッチングさせるのが、最適。
これで割当順が決まったので、更にソートを行い、A[i]を減らしてA[i]F[i]≦最大値となるようにする。
修行回数がK回以下なら、その最大値を達成可能なのでtrue

int N; ll K;
int A[201010], F[201010];
//---------------------------------------------------------------------------------------------------
bool check(ll ma) {
    ll cnt = 0;
    rep(i, 0, N) {
        int ok = 0, ng = A[i] + 1;
        while (ok + 1 != ng) {
            int md = (ok + ng) / 2;
            if (1LL * md * F[i] <= ma) ok = md;
            else ng = md;
        }
        cnt += A[i] - ok;
    }
    return cnt <= K;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> F[i];

    sort(A, A + N);
    sort(F, F + N, greater<int>());

    ll ng = -1, ok = infl;
    while (ng + 1 != ok) {
        ll md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}