実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 189

問題概要

$N$ 個の料理があり、料理 $i$ の甘さは $A_i$ 、しょっぱさは $B_i$ である。これから $N$ 個の料理を好きな順番で食べていくが、食べた料理の甘さの合計が $X$ より大きくなるか、しょっぱさの合計が $Y$ より大きくなった時点で食べるのをやめる。このとき、食べることになる料理の個数の最小値を求めよ。

制約

入力はすべて整数。
$1 \leq N \leq 2 \times 10^5$
$1 \leq X, Y \leq 2 \times 10^{14}$
$1 \leq A_i, B_i \leq 10^9$

考察

2つの条件のうちどちらかが満たされれば良いので、

$(甘さの合計) > X$ となるときの食べる料理の個数の最小値 $x$
$(しょっぱさの合計) > Y$ となるときの食べる料理の個数の最小値 $y$

を求め、最終的な答えを $\min(x, y)$ とすればよい。

$x, y$ はそれぞれ $A_i, B_i$ を降順ソートして順に食べていくことで求められる。

コード

#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()
#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N;
    cin >> N;
    ll X, Y;
    cin >> X >> Y;
    vector<int> A(N), B(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    sort(all(A), greater<int>());
    sort(all(B), greater<int>());

    int idx_1 = 0, idx_2 = 0;
    ll sum = 0;
    rep(i, 0, N)
    {
        sum += A[i];
        idx_1++;

        if (sum > X)
            break;
    }

    sum = 0;
    rep(i, 0, N)
    {
        sum += B[i];
        idx_2++;

        if (sum > Y)
            break;
    }

    cout << min(idx_1, idx_2) << endl;
}