重さが軽い木の実から順番に食べたほうが良いことは明らかです。
よって、 を昇順にソートした後に累積和を取ることによって、 個の木の実を重さの和の最小値を とすると、
は で取得することができます。
また、負の重さの木の実がないことから、 が成り立ちます。
したがって、モンスターごとに食べれる木の実の最大数を二分探索により で求めることができます。
全体でこの問題を でこの問題を解くことができ、十分高速です。
#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; }