ソリの番号を付け替えても答えは変わらないので、\((R_1,R_2, \ldots, R_N)\) が昇順にソートされているとしてよいです。

この仮定の下で \(m\) 台のソリを引くとき、そのソリは \(1,2,\ldots, m\) としてよいので、この問題は \(R_1 + R_2 + \ldots + R_m \leq X\) なる最大の \(m\) を求めることに帰着できます。

これは累積和、すなわち各 \(i\) に対する \(R_1 + R_2 + \ldots + R_i\) の値を前計算しておき、この数列に対して二分探索を行うことで答えを求めることができます。

数列のソートに \(O(N \log N)\)、各クエリで \(O(\log N)\) の時間計算量となるので、全体として \(O((N+Q) \log N)\) の時間計算量でこの問題を解くことができます。

また、この問題ではクエリを先読みすることができるので、クエリを \(X\) の昇順にソートし、尺取り法の要領で答えを求めることもできます。

実装例

#include <iostream>
#include <vector>
#include <algorithm>
#define rep(i, n) for (ll i = 0; i < (n); i++)
using namespace std;
using ll = long long;

int main() {
	int n, q;
	cin >> n >> q;
	vector<ll> r(n);
	rep(i, n) cin >> r[i];
	sort(r.begin(), r.end());
	vector<ll> s(n + 1);
	rep(i, n) s[i + 1] = s[i] + r[i];
	while (q--) {
		ll x;
		cin >> x;
		cout << upper_bound(s.begin(), s.end(), x) - s.begin() - 1 << endl;
	}
}