Hướng dẫn giải của TKNP03: Đếm số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Với mỗi ~X~, đếm số phần tử của dãy lớn hơn hoặc bằng ~X~.
Sub 1: Vét cạn — ~O(n \cdot Q)~, dùng khi ~n \cdot Q \le 10^7~
Mỗi truy vấn duyệt toàn bộ dãy và đếm. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Sắp xếp và lower_bound — ~O((n + Q) \log n)~
Sắp xếp dãy. Các phần tử ~\ge X~ nằm từ vị trí ~lower_bound(X)~ đến hết, nên số lượng bằng ~n - idx~. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
~main~ đọc dữ liệu. Nếu ~n \cdot Q \le 10^7~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, Q;
vector<long long> A;
vector<long long> qs;
// Sub 1: vet can. Moi truy van duyet ca day, dem so phan tu >= X. O(n*Q).
void sub1() {
for (long long x : qs) {
int cnt = 0;
for (int i = 0; i < n; i++)
if (A[i] >= x) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sap xep, so phan tu >= X = n - (vi tri dau tien >= X). O((n + Q) log n).
void sub2() {
sort(A.begin(), A.end());
for (long long x : qs) {
int idx = lower_bound(A.begin(), A.end(), x) - A.begin();
cout << n - idx << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> Q;
A.resize(n);
for (int i = 0; i < n; i++) cin >> A[i];
qs.resize(Q);
for (int i = 0; i < Q; i++) cin >> qs[i];
if ((long long)n * Q <= 10000000) sub1();
else sub2();
return 0;
}
Bình luận