Hướng dẫn giải của TKNP04: Đếm số trong đoạn
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 phần tử ~A_i~, đếm số phần tử ~B_j~ nhỏ hơn ~A_i~. Kết quả in trên một dòng, các số cách nhau bởi dấu cách.
Sub 1: Vét cạn — ~O(n \cdot m)~, dùng khi ~n \cdot m \le 10^6~
Với mỗi ~A_i~, duyệt toàn bộ ~B~ và đếm. Nếu chỉ nộp sub này: đúng 16/20 test.
Sub 2: Sắp xếp B và lower_bound — ~O((n + m) \log m)~
Sắp xếp ~B~. Số ~B_j < A_i~ chính là vị trí ~lower_bound(A_i)~ tính từ đầu mảng. 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 m \le 10^6~ gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<long long> A, B;
// Sub 1: vet can. Voi moi A[i], dem B[j] < A[i] bang hai vong lap. O(n*m).
void sub1() {
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < m; j++)
if (B[j] < A[i]) cnt++;
cout << cnt << (i + 1 < n ? " " : "\n");
}
}
// Sub 2: sap xep B, voi moi A[i] dung lower_bound: so B < A[i]. O((n + m) log m).
void sub2() {
sort(B.begin(), B.end());
for (int i = 0; i < n; i++) {
int cnt = lower_bound(B.begin(), B.end(), A[i]) - B.begin();
cout << cnt << (i + 1 < n ? " " : "\n");
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
A.resize(n);
B.resize(m);
for (int i = 0; i < n; i++) cin >> A[i];
for (int j = 0; j < m; j++) cin >> B[j];
if ((long long)n * m <= 1000000) sub1();
else sub2();
return 0;
}
Bình luận