Hướng dẫn giải của Đếm số (đề KS2 ĐH 2024)
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 truy vấn ~x~, đếm số phần tử của ~A~ lớn hơn ~x~.
Sub 1: Vét cạn — ~O(N \cdot Q)~, dùng khi ~N \cdot Q \le 10^6~
Với mỗi truy vấn, duyệt toàn bộ dãy ~A~ và đếm các phần tử lớn hơn ~x~.
Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Sắp xếp rồi tìm nhị phân — ~O((N + Q) \log N)~
Sắp xếp ~A~ tăng dần. Với mỗi ~x~, dùng upper_bound để tìm vị trí đầu tiên lớn hơn ~x~; số phần tử lớn hơn là ~N - \text{vị trí}~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Nếu ~N \cdot Q \le 10^6~ thì dùng sub 1, còn lại dùng sub 2.
#include <bits/stdc++.h>
using namespace std;
int N, Q;
vector<long long> A, X;
// Sub 1: vet can, moi truy van duyet het day A. O(N*Q). Dung khi N*Q nho.
void sub1() {
for (int i = 0; i < Q; i++) {
int cnt = 0;
for (int j = 0; j < N; j++)
if (A[j] > X[i]) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sap xep A roi dung upper_bound cho moi truy van. O((N + Q) log N).
void sub2() {
vector<long long> B = A;
sort(B.begin(), B.end());
for (int i = 0; i < Q; i++) {
int pos = upper_bound(B.begin(), B.end(), X[i]) - B.begin();
cout << N - pos << "\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];
X.resize(Q);
for (int i = 0; i < Q; i++) cin >> X[i];
if ((long long)N * Q <= 1000000LL) sub1();
else sub2();
return 0;
}
Bình luận