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

問題概要

$N$ 台のソリがあり、ソリ $i$ を引くために必要なトナカイは $R_i$ 匹である。また、各トナカイが引けるソリは高々1台である。以下の形式のクエリが $Q$ 個与えられるので、順に処理せよ。

クエリ :
- 整数 $X$ が与えられるので、 $X$ 匹のトナカイが最大何台のソリを引けるか求めよ。

制約

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

考察

$R_i$ を昇順ソートしたとき、各クエリで求めたいのは $\displaystyle \sum_{i=1}^{m} R_{i} \leq X$ を満たす最大の $m$ である。

この $m$ を愚直に求めようとすると $R_i$ を $i = 1$ から順に足していくことになるが、制約の大きさから、各クエリに対して行っていくと実行時間制限に間に合わない。

そこで、毎回 $R_i$ を最初から足していくのではなくて、事前に $v_i := \displaystyle \sum_{k=1}^{i} R_{k}$ という配列を用意しておき、各クエリではこの (単調増加な) 配列に対して二分探索を行うことで、対数時間でクエリを処理することが可能になる。

配列 $v_i$ は累積和というテクニックで、今回のような「数列上のある範囲の総和を高速で求めたい」ときに有効な手段である。

なお、 $v_0 = 0$ であるから、二分探索で得られたインデックスから $1$ 引く必要があることに注意しよう。

コード

#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)++)

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

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<ll> R(N);
    rep(i, 0, N) cin >> R[i];

    sort(all(R));

    vector<ll> ps(N + 1, 0);
    rep(i, 0, N) ps[i + 1] = ps[i] + R[i];

    while (Q--)
    {
        ll X;
        cin >> X;

        cout << upper_bound(all(ps), X) - ps.begin() - 1 << endl;
    }
}