けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

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

問題概要

 N 台のソリがあり、それぞれトナカイを  A_{1}, A_{2}, \dots, A_{N} 匹必要とする。次の  Q 回のクエリに答えよ。

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

制約

  •  1 \le N, Q \le 2 \times 10^{5}

考えたこと

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

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


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

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

 S_{i} \le X であるような最大の  i

を二分探索法で求めればよい。全体の計算量は  O((N + Q) \log N) となる。

コード

#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;
    }
}