AtCoder ABC 231 C - Counting 2 (4Q, 灰色, 300 点)

鉄則本 B11 とほぼ同じ問題！

• 問題へのリンク

問題概要

身長が であるような 人がいる。以下の 回のクエリに答えよ。

【クエリ】
整数 key が与えられるので、身長が key 以上の人が何人いるかを答えよ。

制約

• 

考えたこと

0-indexed で考えます。

最初に、 を小さい順にソートすることにします。このとき、次の値を求められばよいことになります。

---

A[index] >= key であるような最小の index

---

この値が求められば、答えは N - index と求められます。

そして、この index は、C++ であれば関数 lower_bound() を使用することで求められます (使い方はこの記事など参照)。この関数の実行に要する計算量は です。

全体として、計算量は

• 最初に A をソートする部分：
• 各クエリに答える部分：

より、 となります。

コード

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

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    sort(A.begin(), A.end());
    while (Q--) {
        int x;
        cin >> x;
        int it = lower_bound(A.begin(), A.end(), x) - A.begin();
        cout << N - it << endl;
    }
}