Osmium_1008と課題 [技術室奥プログラミングコンテスト#4 Day1 E]

https://atcoder.jp/contests/tkppc4-1/tasks/tkppc4_1_e

前提知識

• 二分探索

解説

https://atcoder.jp/contests/tkppc4-1/submissions/6663888

扱うものが多いので、固定して考えると考えやすいものを考える。
エナジードリンクをenergy本使用するとする。
すると、飲むべきエナジードリンクは、多く回復するものから飲むのが最適。
これで使用できるエネルギーが決定するので、このエネルギーで最大何個の課題が終わるかが分かる。
これは、課題をエネルギーが小さい方から順番に行っていく。
get(energy) := エナジードリンクをenergy本使用した時に終わる課題の最大数
get関数は単調増加するので、二分探索することができる。
[0,K]の範囲で二分探索をして、N以上となる最小のenergyを見つけると答え。
条件を満たすものがない場合はget(K)が答えになる。

int N, M, K, E, A[201010], B[201010];
//---------------------------------------------------------------------------------------------------
int get(int energy) {
    ll tot = E;
    rep(i, 0, energy) tot += B[i];

    int cnt = 0;
    rep(i, 0, N) {
        if (tot < A[i]) return cnt;
        cnt++;
        tot -= A[i];
    }
    return cnt;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M >> K >> E;
    rep(i, 0, N) cin >> A[i];
    sort(A, A + N);
    rep(i, 0, M) cin >> B[i];
    sort(B, B + M, greater<int>());

    int ans = get(K);
    if (ans < N) {
        cout << "No" << endl;
        cout << ans << endl;
        return;
    }

    int ng = 0, ok = K;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (get(md) == N) ok = md;
        else ng = md;
    }
    cout << "Yes" << endl;
    cout << ok << endl;
}