Hướng dẫn giải của Đếm số (Minh họa TS chuyên PT 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
Mỗi truy vấn cho một số ~x~, cần đếm số phần tử của dãy ~A~ lớn hơn ~x~. Có ~N, Q \le 10^6~ nên mỗi truy vấn không thể duyệt cả dãy.
Sub 1: Vét cạn — ~O(N \cdot Q)~, dùng khi ~N, Q \le 1000~
Với mỗi truy vấn ~x~, duyệt cả dãy và đếm các ~A_i > x~. Nếu chỉ nộp sub này: đúng 8/20 test (đúng hết các test trong miền, 12 test lớn bị quá giờ).
Sub 2: Sắp xếp và tìm kiếm nhị phân — ~O((N + Q) \log N)~
Sắp xếp dãy ~A~ tăng dần. Với mỗi ~x~, dùng upper_bound để tìm vị trí đầu tiên có giá trị lớn hơn ~x~; số phần tử lớn hơn ~x~ bằng ~\text{end} - \text{it}~.
Bẫy cần chú ý: giá trị có thể âm tới ~-10^9~ nên dùng long long; upper_bound (không phải lower_bound) để không tính các phần tử bằng ~x~.
Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
main đọc ~N, Q~, dãy ~A~ và các truy vấn. Nếu ~N, Q \le 1000~ thì gọi sub1, còn lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, q;
long long a[1000005]; // day A
vector<long long> xs; // cac truy van
vector<long long> sorted_a;
// Sub 1: vet can O(N * Q) - moi truy van duyet ca day A. Dung khi N, Q <= 1000.
void sub1() {
for (long long x : xs) {
int cnt = 0;
for (int i = 1; i <= n; i++)
if (a[i] > x) cnt++;
cout << cnt << "\n";
}
}
// Sub 2: sap xep day A, moi truy van dung upper_bound tim so phan tu > x
// Do phuc tap O((N + Q) log N), dung cho N, Q <= 10^6.
void sub2() {
sorted_a.assign(a + 1, a + n + 1);
sort(sorted_a.begin(), sorted_a.end());
for (long long x : xs) {
// vi tri dau tien co gia tri > x
auto it = upper_bound(sorted_a.begin(), sorted_a.end(), x);
cout << (sorted_a.end() - it) << "\n";
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
for (int i = 1; i <= n; i++) cin >> a[i];
xs.resize(q);
for (int i = 0; i < q; i++) cin >> xs[i];
// Du lieu nho (N, Q <= 1000): sub1; du lieu lon: sub2
if (n <= 1000 && q <= 1000) sub1();
else sub2();
return 0;
}
Bình luận