AtCoder ABC 334 D - Reindeer and Sleigh (3Q, 茶色, 400 点)

この回、B と C が異常難易度だったために、D が実際の難易度よりもだいぶ Diff が上がってそうだ！

• 問題へのリンク

問題概要

台のソリがあり、それぞれトナカイを 匹必要とする。次の 回のクエリに答えよ。

【クエリ】
トナカイが 匹いるときに、最大で何台のソリを動かせるかを答えよ。

制約

• 

考えたこと

この手のクエリ処理問題では、まず「単発のクエリの問題だったらどのように解くかを考える」ことが大切だ！

単発のクエリ問題であれば、次の Greedy 解法がとれるだろう。

---

• を小さい順に並び替える
• を小さい順に足していき、 以下である範囲の最大個数を求める

---

この解法をクエリ対応するためには、累積和が使える。つまり、小さい順に並び替えた についての累積和 を求めてあげて、

「 であるような最大の 」

を二分探索法で求めればよい。全体の計算量は となる。

コード

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

int main() {
    long long N, Q;
    cin >> N >> Q;
    vector<long long> R(N), S(N + 1, 0);
    for (int i = 0; i < N; ++i) cin >> R[i];
    sort(R.begin(), R.end());
    for (int i = 0; i < N; ++i) {
        S[i + 1] = S[i] + R[i];
    }
    
    while (Q--) {
        long long X;
        cin >> X;
        int num = upper_bound(S.begin(), S.end(), X) - S.begin();
        cout << num - 1 << endl;
    }
}