Nuts

2 secs 1024 MB

重さが軽い木の実から順番に食べたほうが良いことは明らかです。
よって、 $A$ を昇順にソートした後に累積和を取ることによって、 $i \: (1 \leq i \leq N)$ 個の木の実を重さの和の最小値を $S_i$ とすると、
$S_i$ は $O(1)$ で取得することができます。
また、負の重さの木の実がないことから、 $S_i \leq S_{i+1} \: ( 1 \leq i \leq N - 1)$ が成り立ちます。
したがって、モンスターごとに食べれる木の実の最大数を二分探索により $O( \log N)$ で求めることができます。
全体でこの問題を $O(M \log N)$ でこの問題を解くことができ、十分高速です。

実装例(C++)

#include<bits/stdc++.h>

using namespace std;

int main(){
    int n, m;
    cin >> n >> m;
    vector<int> a(n), b(m);
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    for(int i = 0; i < m; i++){
        cin >> b[i];
    }

    sort(a.begin(), a.end());

    vector<long long> sum(n + 1);
    for(int i = 0; i < n; i++){
        sum[i + 1] = sum[i] + a[i];
    }

    for(int i = 0; i < m; i++){
        int ng = n + 1, ok = 0;

        while(abs(ok - ng) > 1){
            int mid = (ok + ng) / 2;
            if (sum[mid] <= b[i]) ok = mid;
            else ng = mid;
        }
        cout << ok << " ";
    }
    cout << endl;
}