パナソニックプログラミングコンテスト2021(AtCoder Beginner Contest 231) C - Counting 2
問題の要約
N人の生徒からなるクラスがあり,i(1<=i<=N)番目の生徒の身長はAi。
j=1,2,...,Qについて,以下の質問に答えよ。
・N人のうち,身長がxj以上の生徒は何人か?
制約
1<=N,Q<=2*10^5
1<=Ai<=10^9
1<=xj<=10^9
入力
N Q
A1 A2 ... AN
x1
x2
...
xQ
出力
Q行出力
j(1<=j<=Q)行目には身長がxj以上の生徒の数を出力
考え方
1,生徒の番号を1ずらす。
1<=i<=N => 0<=i<=N-1
2,vector<long long>で身長を管理し,ソートして,lower_boundでxj以上の最も左のイテレータを取得。
3,vector<long long>の最後尾のイテレータから2で取得したイテレータの差を取って出力。
実際のプログラム
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
long long N,Q;
cin >> N >> Q;
vector<long long> A(N);
for(long long i = 0; i < N; i++){
cin >> A[i];
}
sort(A.begin(),A.end());
for(long long i = 0; i < Q; i++){
long long x;
cin >> x;
auto itr = lower_bound(A.begin(),A.end(),x);
cout << A.end()-itr << endl;
}
return 0;
}