【ABC144】E - Gluttony

atcoder.jp

解法

最大値の最小化と聞くと二分探索が思い浮かぶ。
そこで答えで二分探索できないか考えてみることにする。

修行なしでメンバーと食べ物を最適にマッチングするには、食べ物を昇順、メンバーを降順に並び替えて同じ番号を組み合わせれば良い。
この組み合わせごとのコストを、修行で二分探索した値まで減らすことをN回繰り返して、修行回数をK回以内に抑えられることができるかを二分探索の判定に使う。

実装

bool isOK(ll mid, ll N, ll K, vector<ll> &A, vector<ll> &F) {
    REP (i, N) {
        // 修行により減らさないといけない成績
        ll remain = max(0LL, A[i] * F[i] - mid);
        // 修行した数を減らす
        K -= myceil(remain, F[i]);
        // 修行回数が足りなければNG
        if (K < 0) return false;
    }
    return true;
}

void solve(long long N, long long K, std::vector<long long> A, std::vector<long long> F){
    sort(rall(A)); // 降順ソート
    sort(all(F)); // 昇順ソート

    ll ng = -1;
    ll ok = INF64;

    // 二分探索
    while (abs(ok - ng) > 1) {
        ll mid = (ok + ng) / 2;
    
        if (isOK(mid, N, K, A, F)) ok = mid;
        else ng = mid;
    }

    cout << ok << endl;
}